[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<<;
}