题解：P11197 [COTS/CETS 2021] 赛狗游戏 Tiket

· · 题解

思路分析

分别令 a_i,b_i,c_i 表示 i 在 P_1,P_2,P_3 中的排名

首先，对于所有满足条件的 (i,j)，可分为以下几种情况。

事实上，我们可以将 T,P_1,P_2,P_3 都反转，把第二类二元组转化为：

和第一类二元组相结合，可以把第一维的限制去掉，这就是一个三维偏序的模板了。

观察数据范围，发现 n\le 5\times 10^5，通常解决三维偏序的算法时间复杂度为 O(n\log^2n),O(n\sqrt n)，都不能在正确的时间内通过本题。

其实三维偏序还存在一个 O(n\log n) 的容斥做法。

我们记 S(a,b) 为存在多少 (i,j) 满足 a_i<a_j,b_i<b_j。然后计算 ans=S(a,b)+S(b,c)+S(a,c)。

这个答案并不是三维偏序的对数，对于每一个三维偏序，我们都将其统计了 3 次（S(a,b),S(b,c),S(a,c) 各有一次贡献）。

对于仅仅只有二维偏序的对数，我们将其统计了 1 次（例如：对于 (i,j)，如果满足 b_i<b_j,c_i<c_j,a_i>a_j，那么它会在 S(b,c) 中贡献为 1，在 S(a,b),S(a,c) 中贡献为 0）。我们要想办法消掉这一部分。

有这么一个结论，三维偏序的对数和仅仅满足二维偏序的对数的和为总对数的一半。

证明：对于任意 (i,j)，如果 (i,j) 是三维偏序，那么 (j,i) 是零维偏序，如果 (i,j) 是二维偏序，那么 (j,i) 是一维偏序。可以自己写几个数手模一下，对于 (i,j) 为零维偏序和一维偏序同样可以证明。

所以对于任意 (i,j)，如果它是三维或二维偏序，那么 (j,i) 一定不是；如果 (i,j) 不是三维或二维偏序，那么 (j,i) 一定是。显然，结论成立。

我们令 ans 减去 \frac{n(n-1)}{2}，此时 ans 中只将每个三维偏序算了两遍，直接取一半输出就可以。

时间复杂度为 O(n\log n)。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int c[N],res,n;
struct node{int a,b,c;}q[N];
bool cmp_a(node a,node b){return a.a<b.a;}
bool cmp_b(node a,node b){return a.b<b.b;}
inline void read(int &a){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return a=x,void();
}
inline void add(int x,int t){
    for(;x<=n;x+=(x&-x))c[x]+=t;
    return;
}
inline int ask(int x){
    int cnt=0;
    for(;x>0;x-=(x&-x))cnt+=c[x];
    return cnt;
}
signed main(){
    read(n);
    for(int i=1,x;i<=n;i++)read(x);
    for(int i=1,x;i<=n;i++)read(x),q[x].a=i;
    for(int i=1,x;i<=n;i++)read(x),q[x].b=i;
    for(int i=1,x;i<=n;i++)read(x),q[x].c=i;
    sort(q+1,q+1+n,cmp_a);
    for(int i=1;i<=n;i++){
        res+=ask(q[i].b);
        add(q[i].b,1);
    }
    for(int i=1;i<=n;i++)add(q[i].b,-1);
    for(int i=1;i<=n;i++){
        res+=ask(q[i].c);
        add(q[i].c,1);
    }
    for(int i=1;i<=n;i++)add(q[i].c,-1);
    sort(q+1,q+1+n,cmp_b);
    for(int i=1;i<=n;i++){
        res+=ask(q[i].c);
        add(q[i].c,1);
    }
    res=(res-(n*(n-1)/2))/2;
    printf("%lld\n",res);
    return 0;
}

参考：在 O(n\log n) 的时间复杂度内计算三维偏序。

如有错误，请指出。