[bzoj 1594]猜数游戏

主要是怎么处理矛盾

矛盾的条件有$2$种:

第一种是当把所有相等的$a$都全部找到后，他们并没有全联通，所以矛盾，因为没有两个是相同的

第二种是在2组$(l,r,a)$,$(l1,r1,a1)$中，$a<a1$并且$(l,r)$ 包含在$(l1,r1)$，矛盾

所以怎么去维护，第一种直接暴力查询，第二种我们可以从大到小排序$minn$，去在线段树中维护并集操作，看一看是否被覆盖即可

此答案具有单调性，所以可以通过二分优化

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

struct node{

    int l,r,minn;

}x[],st[];

int flag[],n,q,maxn,inf=(int)<<;

bool cmp(node x1,node x2){return x1.minn>x2.minn;}

void pushdown(int k,int l,int r){

    if(!flag[k]) return;

    flag[k<<]=flag[k<<|]=;

    flag[k]=;return;

}

void update(int k,int l,int r,int x,int y){

//    cout<<x<<" "<<y<<endl;

    if(x<=l&&r<=y){flag[k]=;return;}

    pushdown(k,l,r);

    int mid=l+r>>;

    if(x<=mid) update(k<<,l,mid,x,y);

    if(mid<y) update(k<<|,mid+,r,x,y);

    flag[k]=flag[k<<]&flag[k<<|];

    return;

}

int query(int k,int l,int r,int x,int y){

    if(x<=l&&r<=y) return flag[k];

    pushdown(k,l,r);

    int mid=l+r>>;

    int kkk=;

    if(x<=mid) kkk&=query(k<<,l,mid,x,y);

    if(mid<y) kkk&=query(k<<|,mid+,r,x,y);

    flag[k]=flag[k<<]&flag[k<<|];

    return kkk;

}

bool check(int len){

//    cout<<"len:"<<len<<endl;return 0;

    memset(flag,,sizeof(flag));

    for(int i=;i<=len;i++) st[i]=x[i];

    sort(st+,st+len+,cmp);

    int j;

    for(int i=;i<=len;i=j+){

        j=i;

        while(j<=len&&st[j].minn==st[i].minn) j++;--j;

        int l1=inf,r1=inf,l2=,r2=;

        for(int k=i;k<=j;k++){

            l1=min(l1,st[k].l);l2=max(l2,st[k].l);

            r1=min(r1,st[k].r),r2=max(r2,st[k].r);

        }

        if(l2>r1) return ;

        if(query(,,n,l2,r1)) return ;

        update(,,n,l1,r2);

    }return ;

}

signed main()

{

    n=read(),q=read();

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

        x[i].l=read(),x[i].r=read(),x[i].minn=read();

    }

    int l=,r=q,mid;

    while(l<=r){

        mid=l+r>>;

        if(check(mid)) maxn=max(maxn,mid),l=mid+;

        else r=mid-;

    }

    if(maxn!=q) cout<<maxn+;

    else cout<<;

}