题目描述 1

有 N 朵花，每朵花有三个属性：花形(S)、颜色(C)、气味(M)，分别用三个整数表示。

现在要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。

定义一朵花 A 比另一朵花 B 要美丽，当且仅当 Sa >= Sb，Ca >= Cb，Ma >= Mb。

显然，两朵花可能有同样的属性。

统计出每个等级的花的数量。

输入格式

• 第一行为 N 和 K, 分别表示花的数量和最大属性值。
• 以下 N 行，每行三个整数 Si、Ci、Mi，表示第 i 朵花的属性。

输出格式

• 包含 N 行，分别表示评级为 0 到 N-1 的每级花的数量。

样例

输入：
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
输出：
3
1
3
0
1
0
1
0
0
1

数据范围与约定

• 1 <= N <= 100000
• 1 <= K <= 200000
• 1 <= Si, Ci, Mi <= K

题目来源

• 陌上花开

算法

(陈丹琦分治，树状数组) $O(n \log^2 n)$

1. 原问题即裸的三维偏序问题，即对于某个三元组 (Si, Ci, Mi)，求出满足 (Sj <= Si, Cj <= Ci, Mj <= Mi) 的不同的 j != i 的个数。
2. 将完全相同的三元组进行合并，接下来的分析过程不考虑有完全相同三元组。
3. 首先按照第一维 S 从小到大排序，S 相同的按照 C 从小到大排序，C 相同的按照 M 从小到大排序。
4. 接下来就需要分治了，分治的目的是统计每个点的答案。
5. 假设当前处理的区间为 [l, r]，中点为 mid，所以两个子区间为 [l, mid] 和 [mid + 1, r]，递归处理两个子区间。
6. 递归结束后，需要考虑如何合并两个子区间。我们可以得知，左子区间所有点的 S 值都小于等于右子区间，所以只需要统计左子区间对右子区间的贡献，不会有右子区间对左子区间的贡献。
7. 将左子区间内部按照 C 从小到大排序，右子区间内部也按照 C 从小到大排序。C 相同的按 M 从小到大排序。
8. 模仿归并排序的时候的合并过程，设两个指针 i 和 j 分别指向两个区间。对于右子区间的每个点，通过树状数组求出左子区间中有多少个点的 M 小于等于当前点的 M。
9. 具体地，对于右子区间的每个点 a[j]，找到点 i 的位置满足 [l, i] 所有的点的 C 都小于等于 a[j].C，且 [l, i] 所有点的 M 都在树状数组上进行了更新。树状数组更新是指，如果一个点的 M 值为 x，则 x 位置加 1 （如果这个点代表多个相同的点，则加上重复点的个数）。对于点 a[j]，在树状数组上询问前缀和 query(a[j].M)，即询问左区间此时有多少个点的 M 值小于等于 a[j].M，累加答案。
10. 最后注意恢复树状数组。（不能通过 memset 强制全体清 0，否则时间复杂度会退化为 $O(n^2)$。因为全体清零每次的时间复杂度都是最初的 n，而不是当前递归区间的长度）。

时间复杂度

• 递归的表达式为 $T(n) = 2T(n/2) + O(n \log n)$，根据主定理，时间复杂度为 $O(n \log^2 n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

struct A {
    int id, count;
    int s, c, m;
};

A a[N], b[N];

int n, m, cnt;
int level[N], ans[N];

int f[M];


inline bool cmp1(const A &x, const A &y) {
    if (x.s != y.s)
        return x.s < y.s;
    if (x.c != y.c)
        return x.c < y.c;
    return x.m < y.m;
}

inline bool cmp2(const A &x, const A &y) {
    if (x.c != y.c)
        return x.c < y.c;
    return x.m < y.m;
}

inline void update(int x, int y) {
    for (; x <= m; x += x & -x)
        f[x] += y;
}

inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += f[x];

    return res;
}

void solve(int l, int r) {
    if (l == r)
        return;

    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);

    sort(a + l, a + mid + 1, cmp2);
    sort(a + mid + 1, a + r + 1, cmp2);

    for (int i = l, j = mid + 1; j <= r; j++) {
        while (i <= mid && a[i].c <= a[j].c) {
            update(a[i].m, a[i].count);
            i++;
        }
        level[a[j].id] += query(a[j].m);
    }

    for (int i = l; i <= mid && a[i].c <= a[r].c; i++)
        update(a[i].m, -a[i].count);
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {
        b[i].id = i;
        scanf("%d%d%d", &b[i].s, &b[i].c, &b[i].m);
    }

    sort(b + 1, b + n + 1, cmp1);

    for (int i = 1; i <= n; i++) {
        if (b[i].s != b[i - 1].s || b[i].c != b[i - 1].c || b[i].m != b[i - 1].m)
            a[++cnt] = b[i];
        a[cnt].count++;
    }

    solve(1, cnt);

    // level[i] 表示 id 为 i 的点的等级。
    // 若某个点自身重复了 x 次，则这个点的等级需要再加上 x - 1。
    for (int i = 1; i <= cnt; i++) {
        level[a[i].id] += a[i].count - 1;
    }

    for (int i = 1; i <= cnt; i++) {
        ans[level[a[i].id]] += a[i].count;
    }

    for (int i = 0; i < n; i++)
        printf("%d\n", ans[i]);

    return 0;
}

题目描述 2

对于序列 A，它的逆序对数定义为满足 i < j，且 Ai > Aj 的数对 (i, j) 的个数。

给 1 到 n 的一个排列，按照某种顺序依次删除 m 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

输入格式

• 输入第一行包含两个整数 n 和 m，即初始元素的个数和删除的元素个数。
• 以下 n 行每行包含一个 1 到 n 之间的正整数，即初始排列。
• 以下 m 行每行一个正整数，依次为每次删除的元素。

输出格式

• 输出包含 m 行，依次为删除每个元素之前，逆序对的个数。

样例

输入：
5 4
1
5
3
4
2
5
1
4
2
输出：
5
2
2
1
解释：
删除数字 5 之前，(1,5,3,4,2) 
删除数字 1 之前，(1,3,4,2)
删除数字 4 之前，(3,4,2)
删除数字 2 之前，(3,2)

数据范围与约定

• N <= 100000
• M <= 50000

题目来源

• Cqoi 2011 动态逆序对

算法

(陈丹琦分治，树状数组) $O(n \log^2 n)$

1. 仿照题目 1，将动态逆序对改造成三维偏序问题。
2. 将删除操作逆转，改为添加操作。即 0 时刻后，我们添加了所有没有删除过的数字，1 时刻后添加了最后一个删除的数字，2 时刻添加了倒数第二个删除的数字，m 时刻后添加了第一个删除的数字。
3. 除了时间外，每个数字还有一个属性为在原数组中的位置 pos。所以，现在每个点有了三个属性，分别为 (time, pos, x)，即时间、位置和这个数字的值。时间有可能相同，但位置一定互不相同。
4. 仿照上一个题目，首先按照时间 time 从小到大排序，时间相同的，按照位置 pos 从小到大排序。
5. 分治递归处理，然后按照位置 pos 从小到大排序两个子区间。此时考虑左子区间对右子区间的贡献，考虑右子区间每个点对整体逆序对数量带来的影响。
6. 对于右子区间的一个点 a[j]，左区间能带来的影响有两方面：一是左子区间中 pos 小于 a[j].pos，但值 x 大于 a[j].x；二是左子区间中 pos 大于 a[j].pos，但值 x 小于 a[j].x。对这两方面的贡献分别用双指针和树状数组统计。

时间复杂度

• 递归的表达式为 $T(n) = 2T(n/2) + O(n \log n)$，根据主定理，时间复杂度为 $O(n \log^2 n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

#define ll long long

const int N = 100010, M = 50010;

int n, m, h[N];

struct A {
    int id;
    int time, pos, x;
}a[N];

ll rev[M];

ll f[N];

inline ll query(int x) {
    ll res = 0;
    for (; x; x -= x & -x)
        res += f[x];

    return res;
}

inline void update(int x, int y) {
    for (; x <= n; x += x & -x)
        f[x] += y;
}

inline bool cmp_time(const A &p, const A &q) {
    if (p.time != q.time)
        return p.time < q.time;
    return p.pos < q.pos;
}

inline bool cmp_pos(const A &p, const A &q) {
    return p.pos < q.pos;
}

void solve(int l, int r) {
    if (l == r)
        return;

    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);

    sort(a + l, a + mid + 1, cmp_pos);
    sort(a + mid + 1, a + r + 1, cmp_pos);

    for (int i = l, j = mid + 1; j <= r; j++) {
        while (i <= mid && a[i].pos < a[j].pos) {
            update(a[i].x, 1);
            i++;
        }
        rev[a[j].time] += i - l - query(a[j].x);
    }

    for (int i = l; i <= mid && a[i].pos < a[r].pos; i++)
        update(a[i].x, -1);

    for (int i = mid, j = r; j >= mid + 1; j--) {
        while (i >= l && a[i].pos > a[j].pos) {
            update(a[i].x, 1);
            i--;
        }
        rev[a[j].time] += query(a[j].x - 1);
    }

    for (int i = mid; i >= l && a[i].pos > a[mid + 1].pos; i--)
        update(a[i].x, -1);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        a[i].time = 0;
        a[i].pos = i;
        scanf("%d", &a[i].x);
        h[a[i].x] = i;
    }

    for (int i = m, j; i >= 1; i--) {
        scanf("%d", &j);
        a[h[j]].time = i;
    }

    sort(a + 1, a + 1 + n, cmp_time);

    solve(1, n);

    for (int i = 1; i <= m; i++)
        rev[i] += rev[i - 1];

    for (int i = m; i >= 1; i--)
        printf("%lld\n", rev[i]);

    return 0;
}