qwq2519 @ 2020-11-05 22:05:54
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
using namespace std;
typedef long long lxl;
typedef pair<int,int> pii;
inline char gt()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <typename T>
inline void read(T &x)
{
register char ch=gt();
x=0;
int w(0);
while(!(ch>='0'&&ch<='9'))w|=ch=='-',ch=gt();
while(ch>='0'&&ch<='9')x=x*10+(ch&15),ch=gt();
w?x=~(x-1):x;
}
template <typename T>
inline void out(T x)
{
if(x<0) x=-x,putchar('-');
char ch[20];
int num(0);
while(x||!num) ch[++num]=x%10+'0',x/=10;
while(num) putchar(ch[num--]);
putchar('\n');
}
const int N=1e5+79;
int n,m;
int a[N];
inline int max(int a,int b)
{
return a>b?a:b;
}
struct node
{
int len,lmax,rmax,maxx,sum;
node() {}
node(int a,int b,int c,int d,int e)
{
len=a;
lmax=b;
rmax=c;
maxx=d;
sum=e;
}
};
struct Segmentree
{
int lc[N<<2],rc[N<<2],lazy[N<<2],sum[N<<2],rev[N<<2];
int root,cnt;
int maxx[N<<2][2],lmax[N<<2][2],rmax[N<<2][2];
Segmentree()
{
memset(lazy,-1,sizeof lazy);
}
inline void pushup(int p,int L,int R)
{
sum[p]=sum[lc[p]]+sum[rc[p]];
int mid((L+R)>>1);
if(sum[lc[p]]==mid-L+1)
lmax[p][1]=mid-L+1+lmax[rc[p]][1];
else lmax[p][1]=lmax[lc[p]][1];
if(sum[lc[p]]==0)
lmax[p][0]=mid-L+1+rmax[rc[p]][0];
else lmax[p][0]=lmax[lc[p]][0];
if(sum[rc[p]]==R-mid)
rmax[p][1]=R-mid+rmax[lc[p]][1];
else rmax[p][1]=rmax[rc[p]][1];
if(sum[rc[p]]==0)
rmax[p][0]=R-mid+rmax[rc[p]][0];
else rmax[p][0]=rmax[rc[p]][0];
maxx[p][1]=max(max( maxx[lc[p]][1],maxx[rc[p]][1]),rmax[lc[p]][1]+lmax[rc[p]][1]);
maxx[p][0]=max(max( maxx[lc[p]][1],maxx[rc[p]][0]),rmax[lc[p]][0]+lmax[rc[p]][0]);
}
inline void pushdown(int p,int L,int R)
{
if(!lc[p]) lc[p]=++cnt;
if(!rc[p]) rc[p]=++cnt;
int mid((L+R)>>1);
if(lazy[p]!=-1)
{
rev[p]=0;//Ô±¾Òª·×ª£¬²»Óã»1
sum[lc[p]]=(mid-L+1)*lazy[p];
sum[rc[p]]=(R-mid)*lazy[p];
lazy[lc[p]]=lazy[rc[p]]=lazy[p];
rev[lc[p]]=rev[rc[p]]=0;
maxx[lc[p]][lazy[p]]=lmax[lc[p]][lazy[p]]=rmax[lc[p]][lazy[p]]=mid-L+1;
maxx[lc[p]][lazy[p]^1]=lmax[lc[p]][lazy[p]^1]=rmax[lc[p]][lazy[p]^1]=0;
maxx[rc[p]][lazy[p]]=lmax[rc[p]][lazy[p]]=rmax[rc[p]][lazy[p]]=R-mid;
maxx[rc[p]][lazy[p]^1]=lmax[rc[p]][lazy[p]^1]=rmax[rc[p]][lazy[p]^1]=0;
lazy[p]=-1;
}
if(rev[p])
{
sum[lc[p]]=(mid-L+1)-sum[lc[p]];
sum[rc[p]]=(R-mid)-sum[rc[p]];
if(lazy[lc[p]]!=-1) lazy[lc[p]]^=1;
else rev[lc[p]]^=1;
if(lazy[rc[p]]!=-1) lazy[rc[p]]^=1;
else rev[rc[p]]^=1;
swap(maxx[lc[p]][0],maxx[lc[p]][1]);
swap(lmax[lc[p]][0],lmax[lc[p]][1]);
swap(rmax[lc[p]][0],rmax[lc[p]][1]);
swap(maxx[rc[p]][0],maxx[rc[p]][1]);
swap(lmax[rc[p]][0],lmax[rc[p]][1]);
swap(rmax[rc[p]][0],rmax[rc[p]][1]);
rev[p]=0;
}
}
inline void build(int &p,int L,int R)
{
if(!p) p=++cnt;
if(L==R)
{
sum[p]=a[L];
if(a[L])
maxx[p][1]=lmax[p][1]=rmax[p][1]=1;
else maxx[p][0]=lmax[p][0]=rmax[p][0]=1;
return ;
}
int mid((L+R)>>1);
build(lc[p],L,mid);
build(rc[p],mid+1,R);
pushup(p,L,R);
}
inline void change(int p,int L,int R,int ll,int rr,int op)
{
pushdown(p,L,R);
if(ll<=L&&rr>=R)
{
if(op==1||op==0)
{
sum[p]=(R-L+1)*op;
lazy[p]=op;
maxx[p][lazy[p]]=lmax[p][lazy[p]]=rmax[p][lazy[p]]=R-L+1;
maxx[p][lazy[p]^1]=lmax[p][lazy[p]^1]=rmax[p][lazy[p]^1]=0;
}
else
{
sum[p]=(R-L+1)-sum[p];
rev[p]^=1;
swap(maxx[p][1],maxx[p][0]);
swap(lmax[p][1],lmax[p][0]);
swap(rmax[p][1],rmax[p][0]);
}
return ;
}
int mid((L+R)>>1);
if(ll<=mid) change(lc[p],L,mid,ll,rr,op);
if(rr>mid) change(rc[p],mid+1,R,ll,rr,op);
pushup(p,L,R);
}
inline int querysum(int p,int L,int R,int ll,int rr)
{
if(!p) return 0;
pushdown(p,L,R);
if(ll<=L&&rr>=R) return sum[p];
int mid((L+R)>>1);
int val(0);
if(ll<=mid) val+=querysum(lc[p],L,mid,ll,rr);
if(rr>mid) val+=querysum(rc[p],mid+1,R,ll,rr);
return val;
}
inline node querymax(int p,int L,int R,int ll,int rr)
{
pushdown(p,L,R);
// if(!p) return 0;
if(ll<=L&&rr>=R) return node
((R-L+1),lmax[p][1],rmax[p][1],maxx[p][1],sum[p]);
int mid((L+R)>>1);
int val(-1);
if(rr<=mid) return querymax(lc[p],L,mid,ll,rr);
else if(ll>mid) return querymax(rc[p],mid+1,R,ll,rr);
else
{
node lnum=querymax(lc[p],L,mid,ll,rr);
node rnum=querymax(rc[p],mid+1,R,ll,rr);
node ans;
ans.sum=lnum.sum+rnum.sum;
if(lnum.sum==lnum.len)
ans.lmax=lnum.sum+rnum.lmax;
else ans.lmax=lnum.lmax;
if(rnum.sum==rnum.len)
ans.rmax=rnum.sum+lnum.rmax;
else ans.rmax=rnum.rmax;
ans.maxx=max(lnum.rmax+rnum.lmax,max(lnum.maxx,rnum.maxx));
return ans;
}
}
} S;
int main()
{
cin>>n>>m;
rep(i,1,n) cin>>a[i];
S.build(S.root,1,n);
int op,l,r;
while(m--)
{
cin>>op>>l>>r;
l++;
r++;
if(op==0) S.change(S.root,1,n,l,r,0);
else if(op==1) S.change(S.root,1,n,l,r,1);
else if(op==2) S.change(S.root,1,n,l,r,2);
else if(op==3) cout<<S.querysum(S.root,1,n,l,r)<<endl;
else cout<<S.querymax(S.root,1,n,l,r).maxx<<endl;
}
return 0;
}
求助
by qwq2519 @ 2020-11-05 22:06:13
不该在考前作死写的。。。心态BOOM