CF1676H2 Maximum Crossings (Hard Version) 题解

· · 题解

题意

一个终端是一排 n 个连接在一起的相等的线段，有两个终端，一上一下。

有一个数组 a_i，代表从上面的终端中第 i 条线段，到下面的终端中第 a_i 条线段，有一条连线。

问这些连线最多有几个交点。

思路

考虑何时两条连线会有交点。

观察样例不难得到，若 i<j 且 a_i≥a_j，则两条连线有交点。

但此时如果仍然用 Easy version 的 O(n^2) 做法，显然会 T 飞。

实际上，这是一个二维偏序问题，复杂度可以做到 O(n\log n)。

我们开一个权值树状数组，将 a_i 按下标顺序插入，

每插入一个 a_i 之前，查询 [a_i,n] 的区间和，累计答案即可。

代码

#include <cstdio>
int T, n, c[200050];long long s;
void C(int x, int k) {for(;x <= n;x += x & -x) c[x] += k;}
int Q(int x, int y)
{
    int r = 0;--x;
    for(;y > x;y -= y & -y) r += c[y];
    for(;x > y;x -= x & -x) r -= c[x];
    return r;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);s = 0;
        for(int i = 1;i <= n;++i) c[i] = 0;
        for(int i = 1, t;i <= n;++i)
            scanf("%d", &t), s += Q(t, n), C(t, 1);
        printf("%lld\n", s);
    }
    return 0;
}