「TJOI 2014」上升子序列

题目大意：给出一个长度为 $n$ 的序列，问有多少个不同的严格上升子序列（位置不同但元素相同算一种）。$n \leq 10^5$

其实这道题并没有什么思维难度……但是我的树状数组差分写得好不熟练啊……

需要注意在离散化的时候，if (a[i] != a[i-1]) ++cnt; a[i] = cnt; 的代码是不对的，因为 a[i-1] 已经修改过了，应该写成 if (b[i] != b[i-1]) ++cnt; a[i] = cnt;

每次给ans和树状数组加上增量，val应该记录当前值。

#include <cstdio>
#include <algorithm>

const int N = 100005, P = 1e9+7;

struct Node {
    int x, y, id;
} a[N];

int sum[N], val[N], vis[N], n;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
bool cmp1(Node a, Node b) {
    return a.y < b.y;
}
bool cmp2(Node a, Node b) {
    return a.id < b.id;
}
int lowbit(int x) {
    return x & (-x);
}
void update(int x, int y) {
    while (x <= n) sum[x] = (sum[x] + y) % P, x += lowbit(x);
}
int query(int x) {
    int res = 0;
    while (x) res = (res + sum[x]) % P, x -= lowbit(x);
    return res;
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i].y = read(), a[i].id = i;
    std::sort(a + 1, a + n + 1, cmp1);
    int cnt = 1; a[1].x = cnt;
    for (int i = 2; i <= n; ++i) {
        if (a[i].y != a[i-1].y) ++cnt;
        a[i].x = cnt;
    }
    std::sort(a + 1, a + n + 1, cmp2);
    int ans = 0;
    for (int i = 1; i <= n; ++i) { //核心代码
        int now = query(a[i].x - 1), inc = (now - val[a[i].x] + P) % P; //当前值和增量
        ans = (ans + inc) % P; //ans加上增量
        val[a[i].x] = now; //val记录当前值
        update(a[i].x, inc); //树状数组加上增量
        if (!vis[a[i].x]) { //树状数组给第一次出现的数加一
            update(a[i].x, 1);
            vis[a[i].x] = 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(n \log n)$