题意：

思路：

1.二分+线段树（但是会TLE 本地测没有任何问题，但是POJ上就是会挂……）

2.二分+并查集

我搞了一下午+一晚上才搞出来…………..（多半时间是在查错）

首先 如果我们想知道这头奶牛之前的奶牛回答的是不是错的怎么办呢？

把回答的A从大到小排个序。这里有几种错的方式：

1. 如果后面的区间完全被前面的区间包含，这是错的
2. 如果有两个不相交的区间的A是一样的，这也是错的（题目保证没有两堆干草的数量是一样的）

注意取相同A的区间的时候不要超过当前二分的mid

并查集的使用也很关键……

如果是第一次覆盖 每回暴力修改一个区间

随后就可以跳着修改了…..

（有很多很多小技巧 感谢NEIGHTHORN的帮助 （和队长的代码））

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

int n,q,ans=0,f[1111111];

struct Section{int from,to,minn;}sec[25555],cpy[25555];

bool cmp(Section a,Section b){return a.minn>b.minn;}

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

inline bool check(int pos){

    for(int i=1;i<=n;i++)f[i]=i;

    for(int i=1;i<=pos;i++)cpy[i]=sec[i];

    sort(cpy+1,cpy+1+pos,cmp);

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

        int x=cpy[i].from,y=cpy[i].to,X=x,Y=y;

        j=i;

        while(cpy[j].minn==cpy[j+1].minn&&j+1<=pos){

            j++;

            x=max(x,cpy[j].from),X=min(X,cpy[j].from);

            y=min(y,cpy[j].to),Y=max(Y,cpy[j].to);

        }

        if(y<x||find(y)<x)return 0;

        while(X<=Y)

            if(find(Y)==Y)f[Y]=find(X-1),Y--;

            else Y=find(Y);

    }

    return 1;

}

int main(){

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

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

        scanf("%d%d%d",&sec[i].from,&sec[i].to,&sec[i].minn);

    int l=1,r=q;

    while(l<=r){

        int mid=(l+r)>>1;

        if(check(mid))l=mid+1;

        else r=mid-1,ans=mid;

    }

    printf("%d\n",ans);

}