「USACO08JAN」Haybale Guessing

题意：给一段长度为 $n$ ，每个位置上的数都不同的序列 $a[1..n]$ 和 $q$ 和问答，每个问答是 $(x, y, r)$ 代表 $RMQ(a, x, y) = r$ , 要你给出最早的有矛盾的那个问答的编号。（此处 $RMQ$ 指最小值）。

要找到最早的有矛盾的那个问答，我们可以采取二分问答，每次处理 $1\sim p$ 内的问答，看看是否出现矛盾。

重点在于如何判断这些问答是否矛盾。

很明显，我们可以把它当作一个区间染色问题，因为求最小值和染色一样，是取最小的那一个，和顺序没有关联，所以我们先把区间内的问答按照给出的 $r$ 值从大到小排序，依次来染色(染色后面会覆盖前面的，正好满足了越来越小，可以求最小值)。

我们把最小值相同的那些区间取出来，求交集和并集(可以转化为求端点)，然后如果满足以下条件，说明出现矛盾：

如果这些区间的交集为空集，那么矛盾(因为保证每个元素不相同，如果两个区间最小值相同但没有交集，那么肯定矛盾)；
如果求得的交集之前已经被染色，即被最小值更大的区间覆盖，那么矛盾(因为之前已经被染色的区间最小值肯定比这个交集的最小值大[已经排序]，例如之前把区间 $[1,3]$ 染色为 $2$ ，但是这次求出的交集为 $[2,2]$ ，最小值为 $1$ ，那么肯定就矛盾了)。

然后对于剩下的情况，把这个并集染色就好了。

现在讲讲如何用并查集处理区间染色问题，可以先去做做这道题LuoguP2391 白雪皑皑。

我们用 $fa[i]$ 来代表第 $i$ 个点左边第一个没有被染色的点的坐标，如果没有被染色，那么我们就将 $fa[r]$ 设为 $getfa(l-1)$ ，同时将 $r--$ ，代表将 $r$ 这个点染色(即到区间外的左边第一个没被染色的点，其实就相当于一个合并操作)。如果被染色了，我们就直接用 $r=getfa(r)$ 来直接找到左边第一个没被访问的点。

然后就愉快的解决了！！(感谢大佬的讲解FALLEN_GEMINI大佬)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,q;
int fa[1010101];
struct node
{
	int l;
	int r;
	int num;
}a[101010],b[101010];
int cmp(node x,node y)
{
	return x.num>y.num;
}
int getfa(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
bool check(int p)//二分答案，考虑在前p个问答里是否出现矛盾
{
	for(int i=1;i<=n;i++)
		fa[i]=i;//初始化
	for(int i=1;i<=p;i++)
		b[i]=a[i];
	sort(b+1,b+p+1,cmp);//排序
	for(int i=1,j;i<=p;i=j+1)
	{
		int lx,rx,ly,ry;//lx与ry构成并集端点,rx,ly构成交集端点
		lx=rx=b[i].l;
		ly=ry=b[i].r;
		j=i;
		while(b[j+1].num==b[j].num&&j+1<=p)
		{
			j++;
			lx=min(lx,b[j].l);
			rx=max(rx,b[j].l);
			ly=min(ly,b[j].r);
			ry=max(ry,b[j].r);//求端点
		}
		if(rx>ly||rx>getfa(ly))//如果左端点大于右端点那么说明是空集，返回false；如果我们当前值所在的交集在之前被其他更大的值所覆盖，那么返回false
			return false;
		while(lx<=ry)
		{
			if(getfa(ry)==ry)
			{
				fa[ry]=getfa(lx-1);
				ry--;
			}
			else
				ry=getfa(ry);
		}
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=q;i++)
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].num);
	int l=1,r=q,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
			l=mid+1;
		else
		{
			r=mid-1;
			ans=mid;
		}
	}
	printf("%d",ans);
	return 0;
}