主要是怎么处理矛盾
矛盾的条件有$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=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } struct node{ int l,r,minn; }x[10000001],st[10000001]; int flag[8000001],n,q,maxn,inf=(int)1<<61; 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<<1]=flag[k<<1|1]=1; flag[k]=0;return; } void update(int k,int l,int r,int x,int y){ // cout<<x<<" "<<y<<endl; if(x<=l&&r<=y){flag[k]=1;return;} pushdown(k,l,r); int mid=l+r>>1; if(x<=mid) update(k<<1,l,mid,x,y); if(mid<y) update(k<<1|1,mid+1,r,x,y); flag[k]=flag[k<<1]&flag[k<<1|1]; 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>>1; int kkk=1; if(x<=mid) kkk&=query(k<<1,l,mid,x,y); if(mid<y) kkk&=query(k<<1|1,mid+1,r,x,y); flag[k]=flag[k<<1]&flag[k<<1|1]; return kkk; } bool check(int len){ // cout<<"len:"<<len<<endl;return 0; memset(flag,0,sizeof(flag)); for(int i=1;i<=len;i++) st[i]=x[i]; sort(st+1,st+len+1,cmp); int j; for(int i=1;i<=len;i=j+1){ j=i; while(j<=len&&st[j].minn==st[i].minn) j++;--j; int l1=inf,r1=inf,l2=0,r2=0; 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 0; if(query(1,1,n,l2,r1)) return 0; update(1,1,n,l1,r2); }return 1; } signed main() { n=read(),q=read(); for(int i=1;i<=q;i++) { x[i].l=read(),x[i].r=read(),x[i].minn=read(); } int l=1,r=q,mid; while(l<=r){ mid=l+r>>1; if(check(mid)) maxn=max(maxn,mid),l=mid+1; else r=mid-1; } if(maxn!=q) cout<<maxn+1; else cout<<0; }