POJ 3657 Haybale Guessing（区间染色并查集）

Haybale Guessing

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2384		Accepted: 645

Description

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 Q_l..Q_h (1 ≤ Q_l ≤ N; Q_l ≤ Q_h ≤ 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.

Input

* 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: Q_l, Q_h, and A

Output

* 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.

Sample Input

Sample Output

3
【分析】数轴上有n个点，没个点上的值都不同。然后给你Q次询问和答案，输入l,r,x，表示在区间[l,r]最小值为x，然后问你最早在哪个地方出现矛盾。
 区间染色问题，可以用并查集来做。先二分出现矛盾的地方p，然后将1~p的询问值按大到小排序，若对于最小值相同的区间中出现不相交的两个区间，那么矛盾出现。
 那么合法的情况就是这些最小值相同的区间必然是两两相交的，那么记录最小的左端点L和最大的右端点R，然后将[L,R]与L-1合并。所以在判断的时候还有判一下
 当前最小值相同的区间的交集是否之前出现过，若出现过，则矛盾。

#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <string>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
using namespace std;
const int N=3e4+5;
const int M=1e6+5;
int n,q,fa[M];
struct interval{
    int x,y,MIN;
    friend bool operator < (interval a,interval b){
        return a.MIN>b.MIN;
    }
}s[N],S[N];
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline bool check(int pos){
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=pos;i++)
        S[i]=s[i];
    sort(S+1,S+pos+1);
    for(int i=1,j;i<=pos;i=j+1){
        int x=S[i].x,X=x,y=S[i].y,Y=y;
        j=i;
        while(S[j+1].MIN==S[j].MIN&&j+1<=pos){
            j++;
            x=max(x,S[j].x),y=min(y,S[j].y);
            X=min(X,S[j].x),Y=max(Y,S[j].y);
        }
        if(x>y||x>find(y))
            return false;
        while(X<=Y){
            if(find(Y)==Y)
                fa[Y]=find(X-1),Y--;
            else
                Y=find(Y);
        }
    }
    return true;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++)
        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].MIN);
    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;
    }
    cout<<ans<<endl;
    return 0;
}

POJ 3657 Haybale Guessing（区间染色 并查集）

POJ 3657 Haybale Guessing（区间染色并查集）