【题解】洛谷P3810【模板】三维偏序（陌上花开）cdq分治+树状数组

有n(1e5)个元素，每个元素有$a_i,b_i,c_i$ai​,bi​,ci​(2e5)三个属性。

设$f(i)$f(i)表示满足$a_j<=a_i$aj​<=ai​且$b_j<=b_i$bj​<=bi​且$c_j<=c_i$cj​<=ci​的$j$j的数量。

对于每个$0<=v<n$0<=v<n，问各有几个$i$i满足$f_i=v$fi​=v。

---

二维偏序的树状数组与cdq分治解法戳我

tyx：这很简单嘛，排序一维，cdq一维，树状数组一维，没了（孙正清烧肖途证明音）。

首先按$a_i$ai​排序，然后开始cdq分治+树状数组。

1. $solve(l,r)$solve(l,r)表示计算$[l,r]$[l,r]对自身的影响，然后把数组按$b_i$bi​排序。步骤如下：
2. 首先取得区间中点$m$m，递归计算$[l,m]$[l,m]，$[m+1,r]$[m+1,r]
3. 归并，将左侧数组和右侧数组合并成$b_i$bi​有序的新数组。
4. 每当要把一个右侧的项放到新数组中时，统计左侧数组对它的贡献，如何统计呢？
5. 此时新数组中所有左侧项的$a_i,b_i$ai​,bi​一定是小于等于这个右侧项的，可以另开一个树状数组维护左侧项的$c_i$ci​。
6. 所以，每当要把一个左侧项放到新数组中时，就将它的$c$c插入到树状数组中。
7. 每当把一个右侧项放到新数组中时，就统计树状数组中有多少个小于等于$c_i$ci​的$c$c，就是对这个点的贡献了。

实现上，如何高效地重复利用树状数组？

在这里，我只想到归并完数据在临时数组里，还没有放回到原数组时，在扫描一次左侧数组，将它们对树状数组的影响消除。

总的复杂度 $T(n) = 2T(n/2) + O(nlogn)$T(n)=2T(n/2)+O(nlogn)，$T(n)=O(nlognlogn)$T(n)=O(nlognlogn)

---

实现时有几个注意事项：

1. 初始的排序，不能只按a增大排序，也要考虑b，c的影响。
2. 具有重复点的情况，要进行查重并统计权值。
3. 归并过程的判断，仍然使用小于等于而不是小于。
4. 可以把答案直接记录在点内。

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 200016, MOD = 1000000007;

struct BinaryIndexTree
{
	int n, bit[M];
	void add(int p, int v)
	{
		if(p==0)
		{
			bit[p] += v;
			return;
		}
		for(; p<=n; p+=p&-p)
			bit[p] += v;
	}
	int sum(int p)
	{
		int ans = bit[0];
		for(; p; p-=p&-p)
			ans += bit[p];
		return ans;
	}
}bit;
struct Point{
	int a, b, c, ans, cnt;
	bool operator==(const Point &y) const
	{
		return a==y.a && b==y.b && c==y.c;
	}
}pt[M], tmp[M];
int cnt[M];
//处理[l,r]对自身的影响，然后按b排序
void solve(int l, int r)
{
	//printf("l=%d r=%d\n",l,r );
	if(l==r) return;
	int m = (l+r)>>1;

	solve(l, m);
	solve(m+1, r);

	for(int i=l, j=m+1, k=l; i<=m||j<=r;)
	{
		if(j>r || (i<=m && pt[i].b<=pt[j].b)) //放左侧
		{
			bit.add(pt[i].c, pt[i].cnt);
			tmp[k++] = pt[i++];
		}
		else //放右侧
		{
			pt[j].ans += bit.sum(pt[j].c);
			tmp[k++] = pt[j++];
		}
	}

	for(int i=l; i<=m; ++i)
		bit.add(pt[i].c, -pt[i].cnt);
	for(int i=l; i<=r; ++i)
		pt[i] = tmp[i];
}
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	int n = read(), k = read(), rn = 0;
	bit.n = k;

	map<tuple<int,int,int>, int> mp;
	for(int i=1; i<=n; ++i)
	{
		pt[i].a = read();
		pt[i].b = read();
		pt[i].c = read();
		pt[i].cnt = 1;
	}

	sort(pt+1, pt+n+1, [](const Point &x, const Point &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;
	});

	for(int i=1; i<=n; ++i)
	{
		if(pt[i]==pt[i-1])
			++pt[rn].cnt;
		else
			pt[++rn] = pt[i];
	}
	for(int i=1; i<=rn; ++i)
		pt[i].ans = pt[i].cnt-1;

	solve(1, rn);

	for(int i=1; i<=rn; ++i)
		cnt[pt[i].ans] += pt[i].cnt;

	for(int i=0; i<n; ++i)
		printf("%d\n",cnt[i] );

    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}