题解 | #小石的妹子#

怎么没有人写 CDQ 分治，模拟赛上用 CDQ 过了这题。

假若一个点并另一个点更重要就连一条边，不难发现只要按照拓扑序简单 即可。

考虑全部按照第一维排序，那么在 CDQ 分治的时候就解决了第一维的限制，在 CDQ 的过程中对左右两边的递归区间处理好按照第二维排序的结果，并枚举左边的点，能连向的右边的点一定是一段前缀，前缀优化建图处理。

通过精细的实现可以做到 考场上随便写的 做法。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+114;
int n,tot;
vector<int> e[maxn];
struct Point{
	int x,y,id;
}P[maxn];
bool cmpx(Point x,Point y){
	return x.x<y.x;
}
bool cmpy(Point x,Point y){
	return x.y<y.y;
}
int pre[maxn];//记录下当前建立的前缀节点的编号 
void CDQ(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	//这里转变为对 y 排序
	sort(P+l,P+mid+1,cmpy);//l - mid
	sort(P+mid+1,P+r+1,cmpy);//mid+1 - r
	//可以用归并做到单 log 但是有点麻烦就算了
	for(int i=l;i<=mid;i++){
		pre[i]=++tot;
		if(i!=l) e[pre[i]].push_back(pre[i-1]);
		e[pre[i]].push_back(P[i].id);
	} 
	int now=l-1;
	for(int i=mid+1;i<=r;i++){
		while(P[now+1].y<P[i].y&&now<mid) now++;
		if(now!=l-1){
			e[P[i].id].push_back(pre[now]);
		}
	}
	return ;
}
int d[maxn],dis[maxn];
void topo(){
	for(int i=1;i<=tot;i++){
		for(int v:e[i]){
			d[v]++;
		}
		dis[i]=0;
	}
	queue<int> q;
	for(int i=1;i<=tot;i++){
		if(d[i]==0){
			if(i<=n) dis[i]=1;
			q.push(i);
		}
	}
	while(q.size()>0){
		int u=q.front();
		q.pop();
		for(int v:e[u]){
			dis[v]=max(dis[v],dis[u]);
			d[v]--;
			if(d[v]==0){
				if(v<=n) dis[v]++;
				q.push(v);
			}
		}
	}
	return ;
}
int main(){
	//freopen("t2.in","r",stdin);
	//freopen("t2.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>P[i].x>>P[i].y,P[i].id=i;
	tot=n;
	sort(P+1,P+n+1,cmpx);
	CDQ(1,n);
	topo();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<'\n';
	} 
	return 0;
}
/*
5 
1 4 
2 2 
3 3 
4 1 
5 5
*/
```cpp