#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
ll sum,lx,rx,sx,size;
}Node[4*200005];
ll n,m,sum,a[200005],lazy[4*200005];
node no;
void UP(ll t) {
Node[t].sum=Node[2*t].sum+Node[2*t+1].sum;
Node[t].sx=max(max(Node[2*t].sx,Node[2*t+1].sx),Node[2*t].rx+Node[2*t+1].lx);
if(Node[2*t].sum==Node[2*t].size) Node[t].lx=Node[2*t].size+Node[2*t+1].lx;
else Node[t].lx=Node[2*t].lx;
if(Node[2*t+1].sum==Node[2*t+1].size) Node[t].rx=Node[2*t+1].size+Node[2*t].rx;
else Node[t].rx=Node[2*t+1].rx;
Node[t].size=Node[2*t].size+Node[2*t+1].size;
}
void Push(int t,int len) {
if(!lazy[t]) return ;
if(lazy[t]==1) { //更0
Node[2*t].sum=len-len/2;
Node[2*t].lx=Node[2*t].rx=Node[2*t].sx=(len-len/2);
lazy[2*t]=1;
Node[2*t+1].sum=len/2;
Node[2*t+1].lx=Node[2*t+1].rx=Node[2*t+1].sx=len/2;
lazy[2*t+1]=1;
lazy[t]=0;
}
else { //更1
Node[2*t].sum=0;
Node[2*t].lx=Node[2*t].rx=Node[2*t].sx=0;
lazy[2*t]=-1;
Node[2*t+1].sum=0;
Node[2*t+1].lx=Node[2*t+1].rx=Node[2*t+1].sx=0;
lazy[2*t+1]=-1;
lazy[t]=0;
}
}
void Build(int t,int l,int r) {
if(l==r) {
Node[t].sum=!a[l];
Node[t].lx=Node[t].rx=Node[t].sx=!a[l];
Node[t].size=1;
return ;
}
int mid=(l+r)/2;
Build(2*t,l,mid);
Build(2*t+1,mid+1,r);
UP(t);
}
void Query(int t,int l,int r,int ll,int rr) {
if(ll<=l&&r<=rr) {
if(no.sum==-1&&no.lx==-1&&no.rx==-1&&no.sx==-1&&no.size==-1) no=Node[t];
else { //个人认为符合特殊性质?即拆分后区间计算顺序是从左往右的
node _no=no;
no.size+=Node[t].size;
no.sum=_no.sum+Node[t].sum;
no.sx=max(max(_no.sx,Node[t].sx),_no.rx+Node[t].lx);
if(_no.sum==_no.size) no.lx=_no.size+Node[t].lx;
else no.lx=_no.lx;
if(Node[t].sum==Node[t].size) no.rx=Node[t].size+_no.rx;
else no.rx=Node[t].rx;
}
return ;
}
Push(t,r-l+1);
int mid=(l+r)/2;
if(ll<=mid) Query(2*t,l,mid,ll,rr);
if(rr>=mid+1) Query(2*t+1,mid+1,r,ll,rr);
}
void Change(int t,int l,int r,int ll,int rr,int to) {
if(ll<=l&&r<=rr) {
if(to==0) {
Node[t].sum=r-l+1;
Node[t].lx=Node[t].rx=Node[t].sx=Node[t].size;
lazy[t]=1;
}
else {
Node[t].sum=0;
Node[t].lx=Node[t].rx=Node[t].sx=0;
lazy[t]=-1;
}
return ;
}
Push(t,r-l+1);
int mid=(l+r)/2;
if(ll<=mid) Change(2*t,l,mid,ll,rr,to);
if(rr>=mid+1) Change(2*t+1,mid+1,r,ll,rr,to);
UP(t);
}
int main() {
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) a[i]=1;
Build(1,1,n);
while(m--) {
ll t,l,r,lt,rt;
scanf("%lld",&t);
if(t==0) {
scanf("%lld%lld",&l,&r);
Change(1,1,n,l,r,0);
}
if(t==1) {
scanf("%lld%lld%lld%lld",&l,&r,<,&rt);
no=(node){-1,-1,-1,-1,-1};
Query(1,1,n,l,r);
ll num=no.size-no.sum;
no=(node){-1,-1,-1,-1,-1};
Query(1,1,n,lt,rt);
if(num>=no.sum) Change(1,1,n,lt,rt,1);
else {
ll fnum=no.sum;
ll _l=lt,_r=rt,ans;
while(_l<=_r) {
ll mid=(_l+_r)/2;
no=(node){-1,-1,-1,-1,-1};
Query(1,1,n,lt,mid);
if(no.sum<=num) ans=mid,_l=mid+1;
else _r=mid-1;
}
Change(1,1,n,lt,ans,1);
}
Change(1,1,n,l,r,0);
}
if(t==2) {
scanf("%lld%lld",&l,&r);
no=(node){-1,-1,-1,-1,-1};
Query(1,1,n,l,r);
printf("%lld\n",no.sx);
}
}
return 0;
}
原来5pts,调了0.5h变成10pts。
实在找不出明显错误了,求查错,谢谢。(代码有看不懂的地方可以问我)