Lvat_s Blog

首先这题显然是线段树

0操作 区间直接赋值为0 很简单

2操作 统计最长连续0的个数 记录lx,rx,mx三个量，随便合并一下就行了，很简单

1操作……

首先需要记录一个sum表示当前区间有多少脑组织

然后二分填满的位置，我偷懒写了线段树外面的二分，然后时间复杂度就多了一个log

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=200005;
 
int n,m;
 
struct SegTree{
int lx,rx,mx,tag,sum,l,r;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag==1){
    tree[rt<<1].tag=1;
    tree[rt<<1|1].tag=1;
    tree[rt<<1].lx=tree[rt<<1].rx=tree[rt<<1].mx=0;
    tree[rt<<1].sum=tree[rt<<1].r-tree[rt<<1].l+1;
    tree[rt<<1|1].lx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=0;
    tree[rt<<1|1].sum=tree[rt<<1|1].r-tree[rt<<1|1].l+1;
    tree[rt].tag=0;
}
if(tree[rt].tag==-1){
    tree[rt<<1].tag=-1;
    tree[rt<<1|1].tag=-1;
    tree[rt<<1].lx=tree[rt<<1].rx=tree[rt<<1].mx=tree[rt<<1].r-tree[rt<<1].l+1;
    tree[rt<<1].sum=0;
    tree[rt<<1|1].lx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=tree[rt<<1|1].r-tree[rt<<1|1].l+1;
    tree[rt<<1|1].sum=0;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mx=max(max(tree[rt<<1].mx,tree[rt<<1|1].mx),tree[rt<<1].rx+tree[rt<<1|1].lx);
tree[rt].lx=tree[rt<<1].lx;tree[rt].rx=tree[rt<<1|1].rx;
if(tree[rt<<1].lx==tree[rt<<1].r-tree[rt<<1].l+1)tree[rt].lx=tree[rt<<1].lx+tree[rt<<1|1].lx;
if(tree[rt<<1|1].rx==tree[rt<<1|1].r-tree[rt<<1|1].l+1)tree[rt].rx=tree[rt<<1|1].rx+tree[rt<<1].rx;
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].mx=tree[rt].lx=tree[rt].rx=0;tree[rt].sum=1;return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Update(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
    tree[rt].tag=val;
    if(val==-1){tree[rt].lx=tree[rt].rx=tree[rt].mx=tree[rt].r-tree[rt].l+1;tree[rt].sum=0;}
    if(val==1){tree[rt].lx=tree[rt].rx=tree[rt].mx=0;tree[rt].sum=tree[rt].r-tree[rt].l+1;}
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Update(rt<<1,l,r,val);
if(r>mid)Update(rt<<1|1,l,r,val);
Pushup(rt);
}
 
int GetSum(int rt,int l,int r){
if(l<=tree[rt].l & tree[rt].r<=r)return tree[rt].sum;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return GetSum(rt<<1|1,l,r);
else if(r<=mid)return GetSum(rt<<1,l,r);
else return GetSum(rt<<1,l,r)+GetSum(rt<<1|1,l,r);
Pushup(rt);
}
 
void Solve(int l0,int r0,int l1,int r1){
int ResL=GetSum(1,l0,r0);
Update(1,l0,r0,-1);
int ResR=GetSum(1,l1,r1);
//printf("Res:%d %d\n",ResL,ResR);
if(ResL+ResR>=r1-l1+1){Update(1,l1,r1,1);/*puts("666!");*/}
else {
    int l=l1,r=r1;
    while(l<=r){
        int mid=l+r>>1,t=GetSum(1,l1,mid);
        if(mid-l1+1-t==ResL){Update(1,l1,mid,1);return;}
        else if(mid-l1+1<ResL+t)l=mid+1;
        else if(mid-l1+1>ResL+t)r=mid-1;
    }
}
}
 
SegTree Merge(SegTree L,SegTree R){
SegTree M;
M.mx=max(max(L.mx,R.mx),L.rx+R.lx);
M.lx=L.lx;M.rx=R.rx;
if(L.sum==0)M.lx=L.lx+R.lx;
if(R.sum==0)M.rx=L.rx+R.rx;
M.sum=max(L.sum,R.sum);
return M;
}
 
SegTree GetMax(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt];
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return GetMax(rt<<1|1,l,r);
else if(r<=mid)return GetMax(rt<<1,l,r);
else {return Merge(GetMax(rt<<1,l,r),GetMax(rt<<1|1,l,r));}
Pushup(rt);
}
 
void Print(){
//puts("233:");
for(int i=1;i<=n;i++)printf("%d ",GetSum(1,i,i));
putchar('\n');
}
 
int main(){
freopen("4592.in","r",stdin);
freopen("4592.out","w",stdout);
scanf("%d %d",&n,&m);
Build(1,1,n);
//Print();
for(int i=1;i<=m;i++){
    int opt,l0,r0,l1,r1;
    scanf("%d %d %d",&opt,&l0,&r0);
    if(opt==1)scanf("%d %d",&l1,&r1);
    if(opt==0)Update(1,l0,r0,-1);
    if(opt==1)Solve(l0,r0,l1,r1);
    if(opt==2)printf("%d\n",GetMax(1,l0,r0).mx);
    //Print();
}
return 0;
}