Submission #58377417

---

Source Code Expand

// LUOGU_RID: 179790464
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
struct BIT{
	int s[N];int lowbit(int x){return x&-x;}
	vector<int> g;
	void updata(int x,int v){for(int i=x;i<=N;i+=lowbit(i)) s[i]+=v;g.push_back(x);}
	void clear(int x){for(int i=x;i<=N;i+=lowbit(i)) s[i]=0;}
	int sum(int x){int ans=0;for(int i=x;i>=1;i-=lowbit(i)) ans+=s[i];return ans;}
	void clear(){for(int i:g) clear(i);g.clear();}
}tree;
int n;
struct node{int x,y,z,ct;}a[N];
bool cmp(node a,node b){return a.x<b.x;}
bool cnm(node a,node b){return a.y<b.y;}
int C(int n,int m){
	if(m==2) return n*(n-1)/2;
	return n*(n-1)*(n-2)/6;
}
int CDQ(int l,int r){
	if(l==r) return void(),a[l].ct=0;
	int mid=(l+r)/2,s=CDQ(l,mid)+CDQ(mid+1,r),p=l;
	sort(a+l,a+mid+1,cnm),sort(a+mid+1,a+r+1,cnm);
	for(int i=mid+1;i<=r;i++){
		while(p<=mid&&a[p].y<a[i].y) tree.updata(a[p++].z,1);
		s+=tree.sum(a[i].z),a[i].ct+=tree.sum(a[i].z);
	}
	tree.clear();return s;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    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,cmp);
	int ans=n+C(n,2)+C(n,3)-CDQ(1,n);
	sort(a+1,a+1+n,cmp),tree.clear();
	for(int i=1;i<=n;i++){
		ans-=C(tree.sum(a[i].y),2);
		tree.updata(a[i].y,1);
		ans+=C(a[i].ct,2)*2;
	}
	tree.clear();
	for(int i=1;i<=n;i++){
		ans-=C(tree.sum(a[i].z),2);
		tree.updata(a[i].z,1);
	}
	sort(a+1,a+1+n,cnm),tree.clear();
	for(int i=1;i<=n;i++){
		ans-=C(tree.sum(a[i].z),2);
		tree.updata(a[i].z,1);
	}
	cout<<ans<<'\n';
	return 0;
}

Submission Info

Judge Result