题解 [美团2018年CodeM大赛-复赛 A] 子序列

子序列

题目描述

给定一个序列，问有多少子序列满足 $\forall i < j，a_i^j < a_j^i$ 。

正解

这种子序列里面元素不独立的题一般不好做，考虑如何将元素的值独立。

$\begin{aligned} \kern{100px} a_i^j &< a_j^i \\ \log a_i^j &< \log a_j^i \\ j \times \log a_i &< i \times \log a_j \\ \frac {\log a_i} {i} &< \frac {\log a_j} {j} \end{aligned}$

现在 $i$ 和 $j$ 的值独立了，发现原问题就是求一个上升子序列个数。

用树状数组单点加，区间求和可以做到 $O(n \log n)$ 。

注意到 $\frac {\log a_i} {i}$ 并不是整数，但其实只要知道相对大小就行，即还需要离散化。

代码

#include <bits/stdc++.h>
#define N 105

using namespace std;

const int mod = 1e9 + 7;
const double eps = 1e-10;

int n;
int a[N];

namespace BIT {
#define lowbit(x) (x & -x)
    int c[N];
    inline void update(int p, int v) {
        for(int i = p; i <= n; i += lowbit(i))
            c[i] = c[i] + v;
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i; i -= lowbit(i))
            res = res + c[i];
        return res;
    }
#undef lowbit
}

struct node {
    int id;
    double x;
}A[N];

bool cmp(const node &u, const node &v) { return u.x < v.x; }

int main() {
    scanf("%d", &n);
    for(int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        A[i].id = i, A[i].x = log(x) / i;
    }

    A[0].x = -1;
    sort(A + 1, A + n + 1, cmp);
    for(int i = 1, rk = 0; i <= n; ++i) {
        if(A[i].x - A[i - 1].x > eps) ++rk;
        a[A[i].id] = rk;
    }

    for(int i = 1; i <= n; ++i)
        BIT::update(a[i], BIT::query(a[i] - 1) + 1);
    printf("%d\n", BIT::query(n));
    return 0;
}