Contest (三维偏序）

一看到题目算法标签 （归并排序，树状数组），貌似和cdq分治有点像，开冲。
对于三元组(x,y,z) 要找到一支队伍a认为自己比另一支队伍b强当且仅当a在至少一场比赛中比b的排名高,使得a自己觉得比b强，b自己也觉得比a强。
样例
4
1 3 1
2 2 4
4 1 2
3 4 3
首先考虑分治；
先对一维的x排序预处理 样例变为
1 3 1
2 2 4
// 分治区间线
3 4 3
4 1 2
这样左区间的x 一定小于右区间的x 所以左区间已经满足了一次比赛成绩高于右区间的人
那么问题来了，剩下两维怎么处理呢
先归并排序把，让两个区间分别以y排序
2 2 4
1 3 1
// 分治区间线
4 1 2
3 4 3
对于右区间的队伍来说，用树状数组来维护第三维z
将左区间y比右区间y小的放入树状数组

int p=l;
    ll res=mid-l+1;
    for(int i=mid+1;i<=r;i++) {
        while(p<=mid && a[p].y<=a[i].y) {
            update(a[p].z,1);
            p++;
        }
        ans+=res-getsum(a[i].z);
    }

因为两个子区间都已经以y排序了，对于当前的a[i]，树状数组里面维护的是右区间的x，y维均大于当前的队伍的z维，所以从统计大于a[i].z的右区间队伍数就行
全代码如下：

#include<bits/stdc++.h>
#define closeiostream ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
#define N 200005
using namespace std;
const ll mod=1e9+7;
struct dw {
    int x,y,z;
}a[N];
bool cmp1(dw d1,dw d2) {
    return d1.x<d2.x;
}
bool cmp2(dw d1,dw d2) {
    return d1.y<d2.y;
}
int n;
ll ans=0;
ll c[N];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
    c[i]+=y;
}
ll getsum(int x)
{
    ll ans=0;
    for(int i=x;i;i-=lowbit(i))
    ans+=c[i];
    return ans;
}
void dvdc(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    dvdc(l,mid);
    dvdc(mid+1,r);
    int p=l;
    ll res=mid-l+1; // 右区间的总队伍数
    for(int i=mid+1;i<=r;i++) {
        while(p<=mid && a[p].y<=a[i].y) {
            update(a[p].z,1);
            p++;
        }
        ans+=res-getsum(a[i].z);
    }
    for(int i=l;i<p;i++) {
        update(a[i].z,-1);  // 清空树状数组，直接memset容易t
    }
    sort(a+l,a+1+r,cmp2); // 偷个懒，就不归并了，
}
int main()
{
    closeiostream;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+1+n,cmp1);
    dvdc(1,n);
    cout<<ans<<endl;
    return 0;
}