问题描述
小 B 和他的 n-1 个朋友们都是 oier 。每个人的 OI 能力分三种:代码能力,思维能力和乱搞能力。
小 B 已经通过某种方式,分别以三种能力为关键字,给所有人从强到弱排好了序,并且不存在两个人某项能力相同
的情况。定义一个人的某项能力值为 n+1- 他的该项能力排名
。为了提高 OI 水平,他们决定互帮互助。具体来说,如果第 个人的三种能力均对应强于第 个人的三种能力,
,那么 可以结为师徒。
小 B 想知道 n 个人中,共有多少对可能的师徒关系。

数据范围：n≤2*10⁶

哎......智商果然不是每个人都有的

cdq分治的时间复杂度为nlog²n

然后就超时了

于是考虑换一个思路，使用容斥

令s(i,j)=[ai>aj]+[bi>bj]+[ci>cj]

令m(i,j)=max(s(i,j),s(j,i))

由于不存在两个人某项能力值相同，所以m(i,j)=2/3

假设有r个(i,j)满足m(i,j)=2，s个(i,j)满足m(i,j)=3

而s即为所求

显然r+s=(n-1)*n/2;

如果对于每两维求“顺序对数”的结果为x（可以用树状数组或归并排序求），那么r+3*s=x

s=(x-(n-1)*n/2)/2

时间复杂度nlogn

然而一般的三位偏序不能这样做，一是因为这里不存在两个人能力值相同的情况，二是因为本题只求总数，不求对于每个人来说他能收几个徒弟

 

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=2*(1e6+5);
int n;
int A[N],B[N],C[N];
long long seed;
long long Rand() {
    return seed = ((seed*19260817) ^ 233333) & ((1<<24)-1);
}
void gen(int *E)
{
    for(int i=1;i<=n;++i) E[i]=i;
    for(int i=1;i<=n;++i) swap(E[i],E[Rand()%i+1]);
}
struct person
{
    int a,b,c;
}p[N];
long long t1,t2,ans;
int tr[N];
void update(int x)
{
    int i=x;
    while(i<=n) tr[i]+=1,i+=(i&(-i));
}
int getsum(int x)
{
    int i=x,ret=0;
    while(i>0) ret+=tr[i],i-=(i&(-i));
    return ret;
}
bool cmp1(person u,person v) {return u.a<v.a;}
bool cmp2(person u,person v) {return u.b<v.b;}
int main()
{
    freopen("b.in","r",stdin); freopen("b.out","w",stdout);
    scanf("%d",&n);
    scanf("%lld",&seed); gen(A);
    scanf("%lld",&seed); gen(B);
    scanf("%lld",&seed); gen(C);
    for(int i=1;i<=n;++i)
        p[i].a=A[i],p[i].b=B[i],p[i].c=C[i];
    t1=1ll*n*(n-1)/2;
    for(int i=1;i<=n;++i) tr[i]=0;
    sort(p+1,p+n+1,cmp1);
    for(int i=1;i<=n;++i)
    {
        t2+=getsum(p[i].b);
        update(p[i].b);
    }
    for(int i=1;i<=n;++i) tr[i]=0;
    for(int i=1;i<=n;++i)
    {
        t2+=getsum(p[i].c);
        update(p[i].c);
    }
    for(int i=1;i<=n;++i) tr[i]=0;
    sort(p+1,p+n+1,cmp2);
    for(int i=1;i<=n;++i)
    {
        t2+=getsum(p[i].c);
        update(p[i].c);
    }
    ans=(t2-t1)/2;
    printf("%lld",ans);
    return 0;
}