loj #2037. 「SHOI2015」脑洞治疗仪

曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

为了简单起见，我们将大脑视作一个 01 序列。

脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）

例如，用上面第

如果再用第

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第

这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。

第一行两个整数

以下

$l_0quad r_0quad l_1quad r_11l0r0l1r1：SHTSC 进行了一次脑洞治疗，用从 l0l_0l0 到 r0r_0r0 的脑组织修补 l1l_1l1 到 r1r_1r1 的脑洞。$

上述区间均在

对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。

样例输入

样例输出

对于 $20%20\%20% 的数据，n,m≤100n, m leq 100n,m≤100；对于 50%50\%50% 的数据，n,m≤20000n, m leq 20000n,m≤20000；对于 100%100\%100% 的数据，n,m≤200000n, m leq 200000n,m≤200000。$

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 200010
using namespace std;
int n,m,a[maxn];
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i]=1;
    int l,r,l1,r1,l2,r2,op;
    while(m--){
        scanf("%d",&op);
        if(op==0){
            scanf("%d%d",&l,&r);
            for(int i=l;i<=r;i++)a[i]=0;
        }
        else if(op==1){
            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            int cnt=0;
            for(int i=l1;i<=r1;i++){
                cnt+=a[i];
                a[i]=0;
            }
            for(int i=l2;i<=r2;i++){
                if(cnt==0)break;
                if(a[i]==0)a[i]=1,cnt--;
            }
        }
        else {
            scanf("%d%d",&l,&r);
            int ans=0,cnt=0;
            for(int i=l;i<=r;i++){
                if(a[i]==0)cnt++;
                else cnt=0;
                ans=max(ans,cnt);
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

50分暴力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200010
using namespace std;
struct node{int l,r,sum,ans,sz;}tr[4*maxn];
int tag[maxn*4];
void tagit(int k,int d){
    if(d==0){
        tr[k].l=tr[k].r=tr[k].ans=tr[k].sz;
        tr[k].sum=0;
    }
    else {
        tr[k].l=tr[k].r=tr[k].ans=0;
        tr[k].sum=tr[k].sz;
    }
    tag[k]=d;
}
node update(node l,node r) {
    node ans;
    ans.l=l.l+(l.sum==0?r.l:0);
    ans.r=r.r+(r.sum==0?l.r:0);
    ans.sz=l.sz+r.sz;
    ans.sum=l.sum+r.sum;
    ans.ans=max(l.r+r.l,max(l.ans,r.ans));
    return ans;
}
void release(int k) {
    if (tag[k]!=-1) {
        int d=tag[k];
        tag[k]=-1;
        tagit(k<<1,d);
        tagit(k<<1|1,d);
    }
}
void build(int k,int l,int r){
    tr[k].l=tr[k].r=tr[k].ans=0;
    tr[k].sz=tr[k].sum=r-l+1;
    tag[k]=-1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void modify_0(int k,int l,int r,int opl,int opr){
    if(l>=opl&&r<=opr){
        tagit(k,0);
        return;
    }
    release(k);
    int mid=(l+r)>>1;
    if(opl<=mid)modify_0(k<<1,l,mid,opl,opr);
    if(opr>mid)modify_0(k<<1|1,mid+1,r,opl,opr);
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
}
int modify_1(int k,int l,int r,int opl,int opr,int i){
    if(l>=opl&&r<=opr){
        int t=tr[k].sz-tr[k].sum;
        if(t<=i){
            tagit(k,1);
            return t;
        }
        release(k);
        int mid=(l+r)>>1;
        int p=modify_1(k<<1,l,mid,opl,opr,i);
        if(p<i)p+=modify_1(k<<1|1,mid+1,r,opl,opr,i-p);
        tr[k]=update(tr[k<<1],tr[k<<1|1]);
        return p;
    }
    release(k);
    int mid=(l+r)>>1,t=0;
    if(opr<=mid)t=modify_1(k<<1,l,mid,opl,opr,i);
    else if(opl>mid)t=modify_1(k<<1|1,mid+1,r,opl,opr,i);
    else {
        t=modify_1(k<<1,l,mid,opl,opr,i);
        if(t<i)t+=modify_1(k<<1|1,mid+1,r,opl,opr,i-t);
    }
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
    return t;
}
node query(int k,int l,int r,int opl,int opr){
    if(l>=opl&&r<=opr)return tr[k];
    release(k);
    int mid=(l+r)>>1;
    if(opr<=mid)return query(k<<1,l,mid,opl,opr);
    else if(opl>mid)return query(k<<1|1,mid+1,r,opl,opr);
    else return update(query(k<<1,l,mid,opl,opr),query(k<<1|1,mid+1,r,opl,opr));
}
int main(){
    freopen("Cola.txt","r",stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        int op;scanf("%d",&op);
        if(op==0){
            int l,r;
            scanf("%d%d",&l,&r);
            modify_0(1,1,n,l,r);
        }
        else if(op==1){
            int l0,r0,l1,r1;
            scanf("%d%d%d%d",&l0,&r0,&l1,&r1);
            node x=query(1,1,n,l0,r0);
            modify_0(1,1,n,l0,r0);
            if(x.sum)modify_1(1,1,n,l1,r1,x.sum);
        }
        else {
            int l,r;
            scanf("%d%d",&l,&r);
            node x=query(1,1,n,l,r);
            printf("%d
",x.ans);
        }
    }
    return 0;
}

100分线段树