[文章目录]
Description
为了提高自己低得可怜的智商，奶牛们设计了一个新的猜数游戏，来锻炼她们的逻辑推理能力。 游戏开始前，一头指定的奶牛会在牛棚后面摆N(1 <= N<= 1,000,000)堆干草，每堆有若干捆，并且没有哪两堆中的草一样多。所有草堆排成一条直线，从左到右依次按1..N编号，每堆中草的捆数在1..1,000,000,000之间。 然后，游戏开始。另一头参与游戏的奶牛会问那头摆干草的奶牛 Q(1 <= Q <= 25,000)个问题，问题的格式如下： 编号为Ql..Qh(1 <= Ql <= Qh <= N)的草堆中，最小的那堆里有多少捆草？ 对于每个问题，摆干草的奶牛回答一个数字A，但或许是不想让提问的奶牛那么容易地得到答案，又或许是她自己可能记错每堆中干草的捆数，总之，她的回答不保证是正确的。 请你帮助提问的奶牛判断一下，摆干草的奶牛的回答是否有自相矛盾之处。
记得好像一年以前大师讲过这道题，当时觉得挺简单的。现在怎么就不会了呢？？？
二分，转化为判定性问题。那么当前回答没有矛盾当且仅当大的答案对应的区间的并集不包含小的答案的交集。【相同权值只能有一堆干草】
可以用并查集维护，对于每个权值，查询对应交集是否没有被覆盖，如果被覆盖则无解。反之将其并集覆盖掉。
注意return false之前别忘了将答案排回去。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
struct node
{
int l,r,w,id;
}a[25100];
bool cmpid(node x,node y){return x.id<y.id;}
bool cmpw(node x,node y){return x.w>y.w;}
int fa[1001000];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool check(int x)
{
for(int i=1;i<=n+1;++i) fa[i]=i;
sort(a+1,a+x+1,cmpw); int p,b=1,e,l,r;
while(b<=x)
{
e=b; l=0xefefefef; r=0x3f3f3f3f;
while(e<x&&a[e+1].w==a[b].w) ++e;
for(int i=b;i<=e;++i) l=max(l,a[i].l),r=min(r,a[i].r);
for(int i=b;i<=e;++i) if(find(l)>r) return sort(a+1,a+x+1,cmpid),false;
for(int i=b;i<=e;++i)
{
p=find(a[i].l);
while(p<=a[i].r)
{
fa[p]=a[i].r+1;
p=find(p+1);
}
}
b=e+1;
}
sort(a+1,a+x+1,cmpid);
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
a[i].id=i;
}
int l=1,r=m+1,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
if(r==m+1) puts("0");
else printf("%d",r);
return 0;
}