Poj 3657 Haybale Guessing（二分+并查集）

题目地址：http://poj.org/PRoblem?id=3657

思路：由于每个位置的数唯一，对于两个区间[l,r]最小值为a、[L,R]最小值为A。若区间[l,r]被区间[L,R]完全包含且a<A，此时存在矛盾且为唯一的矛盾。则可以二分询问Q，判断1---tot内的询问是否合法。每次二分时，将1---tot之间的询问按照最小值从大到小排序（优先处理大数，以后判断时仅需判断小数所在的区间是否被大数所在区间包含）。由于每个数唯一，对于每个最小值相同的区间，判断其交集是否为空或者是否在更大最小值的区间中，此时出现矛盾，继续二分。若未出现矛盾，则将其并集染色（这样判断矛盾时若交集所在区间中无未染色区间，则交集在最小值更大的区间中（最小值从大到小排序，更大最小值的区间已被全部染色，若无未染色区间，则说明此区间在最小值更大区间中））。染色若用线段树，则无优化下会超时，所以可用并查集处理染色：对于一段区间[l,r]若将其染色，则设fa[r]=l-1（不可为l，因为l也为已染色点，例如数据 1 2 1；1 2 2），代表[l,r]中的数已全部染色（从后向前找对于每一个区间中的点都可以直接跳到其父节点，因为该区间已被全部染色），则判断时若l>Find(r)则说明该区间中无未染色点。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=1e6+50;const int maxq=25000+50;struct Node{    int l,r,num;};int n,q;int fa[maxn];Node a[maxq];Node tmp[maxq];int Find(int x){    int r=x;    while(r!=fa[r]) r=fa[r];    int i=x,j;    while(i!=r)    {        j=fa[i];        fa[i]=r;        i=j;    }    return r;}int cmp(Node a,Node b){    return a.num>b.num;}int check(int tot){    for(int i=1; i<=n; i++) fa[i]=i;    for(int i=1; i<=tot; i++) tmp[i]=a[i];    sort(tmp+1,tmp+tot+1,cmp);    for(int i=1,j; i<=tot; i=j+1)    {        j=i;        int l=tmp[i].l,r=tmp[i].r;        int L=tmp[i].l,R=tmp[i].r;        while(j<tot&&tmp[j].num==tmp[j+1].num)        {            j++;            l=max(l,tmp[j].l),r=min(r,tmp[j].r);    //取交集            L=min(L,tmp[j].l),R=max(R,tmp[j].r);    //取并集        }        if(l>r||l>Find(r)) return 0;    //为空或无未染色点        while(L<=R)        {            if(Find(R)==R)            {                fa[R]=Find(L-1);     //染色                R--;            }            else R=fa[R];     //直接跳转到其父节点        }    }    return 1;}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        {            ans=mid;            r=mid-1;        }    }    printf("%d/n",ans);    return 0;}