NC13947 contest(CDQ分治+树状数组+三维偏序)

题目链接

题意：






题解：

AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll n,ans,c[maxn];
struct node{
    ll a,b,c;
}p[maxn],p1[maxn];
bool cmp(node a,node b){
    return a.a<b.a;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,ll v){
    while(x<maxn){
        c[x]+=v;
        x+=lowbit(x);
    }
}
ll query(int x){
    ll res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    cdq(l,mid);cdq(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(p[i].b<p[j].b)add(p[i].c,1),p1[k++]=p[i++];
        else ans+=query(p[j].c),p1[k++]=p[j++];
    }
    while(i<=mid)add(p[i].c,1),p1[k++]=p[i++];
    while(j<=r)ans+=query(p[j].c),p1[k++]=p[j++];
    for(int i=l;i<=mid;i++)add(p[i].c,-1);
    for(int i=l;i<=r;i++)p[i]=p1[i];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b>>p[i].c;
    sort(p+1,p+1+n,cmp);
    cdq(1,n);
    cout<<n*(n-1)/2-ans;
    return 0;
}