P2898 [USACO08JAN] Haybale Guessing G 题解

并查集好题

首先我们知道并查集是可以维护一个区间的覆盖问题的，具体操作就是，对于一个区间，我们让所有的点都有一个指针，这个指针指向这个区间的右端点+1（具体操作可以每个点指向右边，这样后面我们查到一个点的时候用路径压缩就可以了，能从\(\Theta(nlogn)\)变成\(\Theta(n)\) ），这样我们可以让整个区间都以此点为代表元。当查到某个点时，我们用路径压缩（前面说了为什么要用路径压缩）的find，就可以找到这个区间的右端点（即这个点右边被覆盖的最远的点），如果这个点大于等于当前我们要查有没有被覆盖的的区间的右端点，那么这个区间被覆盖了。

那么我们就可以做这道题了。

由于没有修改，自然想到可以离线下来，暴力二分去找第一个不符合的。
考虑如何判断当前问题是否矛盾。

首先我们来分析一下不合法的有哪几种情况：

一、如果两个区间的最小值相等，但没有交集。
二、如果一个小的区间被大的区间覆盖了。

什么意思呢，首先我们观察到题目说没有相等的数，于是我们可以肯定对于两个不相交的区间没有相同的最小值。然后，如果一个最小值较大的区间里有一段的最小值比他还小，那么不合法。读者可以自己想想是不是这两种情况涵括了所有不合法的可能。

因此我们很自然地想到（因为在相等区间内判断交集是否为空，在不等区间内判断大的是否包含小的，只和大小有关，而跟具体数值无关，也就是说我们只需要大小关系），可以把mid之前的所有询问从大到小排个序，对于每个区间：
1.如果和之前的区间值相等，那么判断交集是否为空。
2.如果和之前的不等（说明这个区间的值肯定比前面的要小），判断这个区间所在区间是否被前面的区间包含了。

注意：对于所有值的区间，覆盖关系就这样抽离，变得跟值没有关系了，所以我们才可以共用一个并查集。

还有就是程序实现逻辑可能和我们思考的顺序略有差别，这个请看下文。
其次你会发现只有每个值相同的区间求了交集，并且对区间内所有点进行覆盖（及开头说的那些操作），我们才能很方便的求出是否被前面的区间覆盖，一环套一环。
两个小小的问题：如果和之前的区间相等，怎么求交集呢？如果和之前的区间值不等，我们怎么判断包含呢？
一、我们可以维护\(lx\),\(ln\),\(rx\),\(rn\),\(p\)分别表示最大/最小的左端点，最大/最小的右端点，当前值，然后就可以方便求并集。
判断交集是否为空自然就是\(lx\)是否大于\(rn\)。
二、对于不同值的区间，可能要稍微麻烦一点，我们需要把这个区间全部找完才能判断和更新覆盖，所以这一部分，我们要放到这个值后面一个值时滞后操作。同时呢，我们在值不同的时候还要更新\(lx\),\(ln\),\(rx\),\(rn\),\(p\)，这样才能构成一个逻辑闭环。
所以我们在总结出程序逻辑下的操作：对于所有值相同的区间，即
相等时：求并集，更新四个值，并查一下是否合法。以下简记为操作一。
不等时：查一下这个值的上一个值是否被覆盖，然后对上一个值的所有区间进行覆盖，再更新五个值（这次更新就让当前值成为下一轮的操作对象了）。以下简记为操作二。
举个例子：

代码：

#include<bits/stdc++.h>
using namespace std;
int n,q,fa[1000005],l,r,mid,ln,lx,rn,rx,p;
struct Quest{
	int ls,rs,x,id;
}co[25005],qu[25005];
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
bool cmp(Quest a,Quest b){
	return a.x>b.x;
}
bool check(int x){
	for(int i=1;i<=x;++i) qu[i]=co[i];
	sort(qu+1,qu+x+1,cmp);
	ln=lx=qu[1].ls,rn=rx=qu[1].rs,p=qu[1].x;
	for(int i=1;i<=n+1;++i) fa[i]=i; 
	for(int i=2;i<=x;++i){
		if(qu[i].x==p){
			ln=min(qu[i].ls,ln);
			lx=max(qu[i].ls,lx);
			rn=min(qu[i].rs,rn);
			rx=max(qu[i].rs,rx);
			if(lx>rn) return false;
		}
		else{
			if(find(lx)>rn) return false;
			for(int j=find(ln);;j=find(j+1))
				if(j>rx) break;
				else fa[j]=fa[j+1];
			p=qu[i].x;
			lx=ln=qu[i].ls;
			rx=rn=qu[i].rs;
		}
	}
	return find(lx)<=rn;
}
int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=q;++i) scanf("%d %d %d",&co[i].ls,&co[i].rs,&co[i].x);
	l=0,r=q+1;
	while(l<r){
		mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	if(r==q+1) printf("0");
	else printf("%d",l);
	return 0;
}

这道题好的原因不仅是思路巧妙，更因为这是一种并查集的经典用法，建议学并查集的好好思考。