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+;

const int M=1e6+;

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=;i<=n;i++)

        fa[i]=i;

    for(int i=;i<=pos;i++)

        S[i]=s[i];

    sort(S+,S+pos+);

    for(int i=,j;i<=pos;i=j+){

        int x=S[i].x,X=x,y=S[i].y,Y=y;

        j=i;

        while(S[j+].MIN==S[j].MIN&&j+<=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-),Y--;

            else

                Y=find(Y);

        }

    }

    return true;

}

int main(){

    scanf("%d%d",&n,&q);

    for(int i=;i<=q;i++)

        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].MIN);

    int l=,r=q,ans=;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid))

            l=mid+;

        else

            r=mid-,ans=mid;

    }

    cout<<ans<<endl;

    return ;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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