洛谷P3810 【模板】三维偏序（陌上花开）

$Description$Description

有$n$n个元素，每个元素有$a_i,b_i,c_i$ai​,bi​,ci​三个属性，设$f(i)$f(i)表示满足$a_j\leq a_i,b_j\leq b_i,c_j\leq c_i$aj​≤ai​,bj​≤bi​,cj​≤ci​的$j$j的数量，对于$d\in[0,n-1]$d∈[0,n−1]，求满足$f(i)=d$f(i)=d的数量

---

$Solution$Solution

经典的三维偏序问题，让我们从最基本的二维偏序开始讲起

二维偏序就是排序去掉一维，剩下一维树状数组或归并排序（$cdq$cdq）求逆序对的方法

现在升级到三维偏序，怎么做呢？

首先仍然是排序去掉一维，然后下一维$cdq$cdq分治套树状数组就解决了，当然也可以$cdq$cdq分治再套$cdq$cdq

那能不能树状数组套树状数组呢？空间太大！用$map$map多一个$log$log，不过你也可以像$ctsc2019rk1$ctsc2019rk1的$rqy$rqy大爷那样打一个哈希表，不过这里不推荐

听说还有平衡树套树状数组？本蒟蒻不会呀QWQ

$P.S:$P.S:由于本题是$\leq$≤，所以打树状数组的同学对于$=$=这种情况要特殊处理哦

时间复杂度？$O(nlognlogk)\approx O(nlog^2n)$O(nlognlogk)≈O(nlog2n)

等等！！！
根据这个复杂度，貌似$cdq$cdq套树状数组的时候不用$O(n)$O(n)合并了耶，直接$O(nlogn)$O(nlogn)排序就好了鸭，反正这样的复杂度也是双$log$log（懒人专属鸭）

---

$Code$Code【$cdq$cdq套$cdq$cdq】

#include<cstdio> 
#include<cctype>
#include<algorithm>
using namespace std;int ans[100010],n,k,d[100010];//俺觉得俺的代码通俗易懂，所以俺不给俺的代码加注释，等等，好像已经加了QWQ
inline long long read()
{
    char c;int d=1;long long f=0;
    while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;
    while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
struct node
{
	int x,y,z,*ans;bool b;
	inline void rd(){x=read();y=read();z=read();return;}
	inline bool operator ==(const node &a){return x==a.x&&y==a.y&&z==a.z;}
}a[100010],b[100010],c[100010];
inline bool cmp(node x,node y){return x.x<y.x||x.x==y.x&&x.y<y.y||x.x==y.x&&x.y==y.y&&x.z<y.z;}
inline void cdq2(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	cdq2(l,mid);cdq2(mid+1,r);
	for(register int i=l,j=l,k=mid+1,cnt=0;i<=r;i++)
	{
		if((k>r||b[j].z<=b[k].z)&&j<=mid) c[i]=b[j++],cnt+=c[i].b;
		else {c[i]=b[k++];if(!c[i].b) *c[i].ans+=cnt;}
	}
	for(register int i=l;i<=r;i++) b[i]=c[i];
	return;
}
inline void cdq(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	cdq(l,mid);cdq(mid+1,r);
	for(register int i=l,j=l,k=mid+1;i<=r;i++)
	{
		if((k>r||a[j].y<=a[k].y)&&j<=mid) b[i]=a[j++],b[i].b=1;
		else b[i]=a[k++],b[i].b=0;
	}
	for(register int i=l;i<=r;i++) a[i]=b[i];
	cdq2(l,r);
	return;
}
signed main()
{
	n=read();k=read();
	for(register int i=1;i<=n;i++) a[i].rd(),a[i].ans=&ans[i];
	sort(a+1,a+1+n,cmp);
	for(register int i=n-1;i;i--) if(a[i]==a[i+1]) *a[i].ans=*a[i+1].ans+1;
	cdq(1,n);
	for(register int i=1;i<=n;i++) d[ans[i]]++;
	for(register int i=0;i<n;i++) printf("%d\n",d[i]);
}