每日一题-Contest

Contest
本来以为要cdq什么的
看了题解之后发现它的排名是不重的（题目里好像没说啊）。

那么我们可以发现，对于两个三元组，如果对答案造成贡献，那么它们的关系一定是两个大于一个小于 或是两个小于一个大于，那么我们对任意两个求逆序对，这个三元组恰好被计算两次。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("Yes") 
#define B puts("No")
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll mo=1e9+7;
ll ans;
int n;
struct node{
	int x,y,z;
}; 
node a[N];
int c[N];
int lowbit(int x){
	return x&(-x);
}
void upd(int x){
	for (;x<N;x+=lowbit(x)) {
		c[x]++;
	}
}
ll ask(int x){
	ll s=0;	
	for (;x;x-=lowbit(x)){
		s+=c[x];
	}
	return s;
}
bool cmp1(node a,node b){
	return a.x<b.x;
}
bool cmp2(node a,node b){
	return a.y<b.y;
}
bool cmp3(node a,node b){
	return a.z<b.z;
}
int main(){
	
//	freopen("data.in","r",stdin);		
	scanf("%d",&n);
	fo(i,1,n) {
		scanf("%d %d %d",&a[i].x, &a[i].y, &a[i].z);
	}
	
	memset(c,0,sizeof(c));
	sort(a+1,a+n+1,cmp1);
	fo(i,1,n) {
		ans+=i-1-ask(a[i].y);
		upd(a[i].y);
	}
	
	memset(c,0,sizeof(c));
	fo(i,1,n) {
		ans+=i-1-ask(a[i].z);
		upd(a[i].z);
	}
	
	memset(c,0,sizeof(c));
	sort(a+1,a+n+1,cmp2);
	fo(i,1,n) {
		ans+=i-1-ask(a[i].z);
		upd(a[i].z);
	}
	
	printf("%lld",ans/2);
	return 0;
}