[USACO08JAN]Haybale Guessing G
题面翻译
给一个长度为 \(n\) 的数组 \(q\) 个条件，数组中的数字互不相同，每个条件格式形如 \(l_i,r_i,x_i\) 表示这个数组的区间 \([l_i,r_i]\) 内的最小值为 \(x_i\)，输出最早与前面的条件有矛盾的条件的编号，如果所有条件都不发生矛盾，输出 \(0\)。
输入格式
第一行两个整数，分别是 \(n\) 和 \(q\)。
第二行至第 \(q+1\) 行，每行三个整 \(l_i,r_i,x_i\) 描述一个条件。
输出格式
仅一个整数，表示最早发生矛盾的条件的编号。如果所有条件都没有发生矛盾，输出 \(0\)。
题目描述
The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.
A designated 'Hay Cow' hides behind the barn and creates N (1 ≤ N ≤ 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.
The other cows then ask the Hay Cow a series of Q (1 ≤ Q ≤ 25,000) questions about the the stacks, all having the same form:
What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ≤ Ql ≤ N; Ql ≤ Qh ≤ N)?The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.
Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.
输入格式
* Line 1: Two space-separated integers: N and Q
* Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Ql, Qh, and A
输出格式
* Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise, print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.
样例 #1
样例输入 #1
20 4
1 10 7
5 19 7
3 12 8
11 15 12
样例输出 #1
3
常见二分，二分第一个编号。注意这里当初也走了弯路，不需判断\(mid\)是否为第一个，因为后面右端点还会左移，只要判断是否有矛盾就好了。
然后就是重点——并查集的使用
观察这一段二分内的代码：
bool check(int st)
{
sort(a+1,a+st+1,cmp);
for(int i=1;i<=n+1;i++)
f[i]=i;
int p=a[1].mi,li,ri,la,ra;
li=la=a[1].l;
ri=ra=a[1].r;
for(int i=2;i<=st;i++)
if(a[i].mi==p)
{
li=min(li,a[i].l);
la=max(la,a[i].l);
ri=min(ri,a[i].r);
ra=max(ra,a[i].r);
if(ri<la) return 0;
}
else
{
if(fi(la)>ri) return 0;
for(int j=fi(li);;j=fi(j+1))
if(j>ra) break;
else f[j]=f[j+1];
p=a[i].mi;
li=la=a[i].l;
ri=ra=a[i].r;
}
if(fi(la)>ri) return 0;
else return 1;
}
看起来很不知所谓，甚至像是错误的，其实是一种非常简练高效巧妙的写法。
通过分析可以得知，题目中语句之间的矛盾只有两种：
- 同一段区间所包含的最小值不同
- 同一最小值所处的区间不同
第二种情况很好判断，只要记录\(mi\)值相同时，最大左端点和最小右端点是否有交叉区间就行了。
而对于第一种情况，考虑我们将二分范围内的语句\(mi\)值大小按照从大到小排序，当我们知道前面较大的\(mi\)值覆盖范围时，只要判断目前的最小范围能否被前面覆盖，若能被覆盖，则矛盾。
因为前面所枚举的\(mi\)值都大于当前值，所以不管是哪个只要能覆盖住就行；又因为只需判断是否矛盾而不需判断个数，所以只要判断最可能的那一种情况就得了。
下面说并查集。
这里的并查集\(f[x]\)保存的是\(x\)点向右第一个没有被覆盖的点。
原理参照这里：
有如下问题：
长为nn的序列，开始均无颜色，
有mm个操作，每次将ll到rr的数全染成cc色，
求最终的序列。
我们考虑将染色反着来，则一个数若被染色一次，
则这就是它的最终颜色，不会改变。
所以下次若在遇到这个数则需要跳过，
也就是对已经染色的区间[l,r][l,r]，我们令其中的所有数都有一个指针，
以指向右边第一个还没有操作的数。
于是我们令father[i]father[i]表示ii右边（包括ii本身）第一个没有染色的数，
将ii染色后，令father[i] = find(i + 1)father[i]=find(i+1),
之后就是正常的并查集操作了。
然后这题是个特例，染色虽然是正着来的，但染的颜色全是一种，
只存在0 - >10−>1，染一次则以后不变色，所以也可用这种方法做。
这里差不多也就是这样的情况了。
标签：游戏,..,染色,mi,矛盾,Hay,000,反思,猜数 From： https://www.cnblogs.com/curly619/p/17090526.html