Contest

代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN=2e5+5;
int n,m;
long long ans;
struct node
{
int x,y,z;
}a[MAXN],b[MAXN];
bool cmp(node p,node q)
{
if(p.x!=q.x)
return p.x < q.x;
if(p.y!=q.y)
return p.y < q.y;
return p.z < q.z;
}
int c[MAXN];
void add(int x,int y)
{
while(x<MAXN)
{
c[x]+=y;
x+=x&(-x);
}
}
int inquire(int x)
{
int cns=0;
while(x)
{
cns+=c[x];
x-=x&(-x);
}
return cns;
}
void abc(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
abc(l,mid);
abc(mid+1,r);
int t=0,p1=l,p2=mid+1;
while(p1<=mid && p2<=r)
{
if(a[p1].y<=a[p2].y)
{
add(a[p1].z,1);
b[++t]=a[p1++];
}
else
{
ans+=inquire(a[p2].z);
b[++t]=a[p2++];
}
}
while(p1<=mid)
{
add(a[p1].z,1);
b[++t]=a[p1++];
}
while(p2<=r)
{
ans+=inquire(a[p2].z);
b[++t]=a[p2++];
}
for(int i=l;i<=mid;i++)add(a[i].z,-1);
for(int i=1;i<=t;i++)
{
a[l+i-1]=b[i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
sort(a+1,a+n+1,cmp);
abc(1,n);
ans=(1lln(n-1)/2)-ans;
printf("%lld\n",ans);
return 0;
}</algorithm></cstring></cstdio></iostream>