不正经题解|同学的红眼

这题是三维偏序魔板题，赛时根本做不了一点（不会cdq），赛后看了一下oiwiki又抄袭借鉴了一下官方题解终于过了，这题还是非常难得
给出全题最短用时AC代码（CDQ分治+树状数组+排序+双指针）:

#include <iostream>
#include <algorithm>
#pragma GCC optimize(3,"Ofast","inline") //题目说注意常数优化那我就来卡常（
#pragma GCC optimize(2,"Ofast","inline")
#pragma GCC optimize(1,"Ofast","inline")
using namespace std;
const int N=2e5+5,M=1e4+5;
struct data{
	int a,b,c,res,val,id;
}e[N];
int ans[N],L[N],R[N],c[M],K;
int cmp1(data x,data y) {
	if (x.a!=y.a) return x.a>y.a;
	if (x.b!=y.b) return x.b>y.b;
	return x.c>y.c;
}
int cmp2(data x,data y) {
	if (x.b!=y.b) return x.b>y.b;
	if (x.c!=y.c) return x.c>y.c;
	return x.a>y.a;
}
int lowbit(int x) {
	return x&(-x);
}
void add(int k,int x) {
	while (k<=K) {
		c[k]+=x;
		k+=lowbit(k);
	}
}
int getsum(int k) {
	int sum=0;
	while (k>0) {
		sum+=c[k];
		k-=lowbit(k);
	}
	return sum;
}
void CDQ(int l,int r) {
	if (l>=r||L[l]==L[r]) return;
	int mid=L[(l+r)>>1];
	if (e[mid].a==e[mid+1].a) {
		mid--;
	}
	if (mid<l) {
		mid=R[(l+r)>>1];
		if (mid==r) return;
	}
	CDQ(l,mid);
	CDQ(mid+1,r);
	sort(e+l,e+mid+1,cmp2);
	sort(e+mid+1,e+r+1,cmp2);
	int i,j;
	for (i=l,j=mid+1;j<=r;j++) {
		for (;i<=mid&&e[i].b>e[j].b;i++) {
			add(e[i].c,e[i].val);
		}
		e[j].res+=getsum(K)-getsum(e[j].c);
	}
	for (int k=l;k<i;k++) {
		add(e[k].c,-e[k].val);
	}
}
int main() {
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d %d %d",&e[i].a,&e[i].b,&e[i].c);
		e[i].id=i;
		e[i].val=max(max(e[i].a,e[i].b),e[i].c);
		K=max(K,e[i].val);
	}
	sort(e+1,e+1+n,cmp1);
	for (int i=1;i<=n;i++) {
		if (e[i].a!=e[i-1].a) {
			L[i]=i;
		}else {
			L[i]=L[i-1];
		}
	}
	for (int i=n;i>=1;i--) {
		if (e[i].a!=e[i+1].a) {
			R[i]=i;
		}else {
			R[i]=R[i+1];
		}
	}
	CDQ(1,n);
	for (int i=1;i<=n;i++) {
		ans[e[i].id]+=e[i].res;
	}
	for (int i=1;i<=n;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
}