#2037. 「SHOI2015」脑洞治疗仪

题目描述

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

为了简单起见，我们将大脑视作一个 01 序列。111 代表这个位置的脑组织正常工作，000 代表这是一块脑洞。

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

例如，用上面第 888 号位置到第 101010 号位置去修补第 111 号位置到第 444 号位置的脑洞，我们就会得到：

如果再用第 111 号位置到第 444 号位置去修补第 888 号位置到第 101010 号位置：

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

如果再用第 777 号位置到第 101010 号位置去填补第 111 号位置到第 666 号位置：

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

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

输入格式

第一行两个整数 nnn、mmm，表示 SHTSC 的大脑可分为从 111 到 nnn 编号的 nnn 个连续区域，有 mmm 个操作。

以下 mmm 行每行是下列三种格式之一：

0lr0\quad l\quad r0lr：SHTSC 挖了一个范围为 [l,r][l, r][l,r] 的脑洞。
1l0r0l1r11\quad l_0\quad r_0\quad l_1\quad r_11l0r0l1r1：SHTSC 进行了一次脑洞治疗，用从 l0l_0l0 到 r0r_0r0 的脑组织修补 l1l_1l1 到 r1r_1r1 的脑洞。
2lr2\quad l\quad r2lr：SHTSC 询问 [l,r][l, r][l,r] 区间内最大的脑洞有多大。

上述区间均在 [1,n][1, n][1,n] 范围内。

输出格式

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

样例

样例输入

样例输出

数据范围与提示

对于 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=;i<=n;i++)a[i]=;

    int l,r,l1,r1,l2,r2,op;

    while(m--){

        scanf("%d",&op);

        if(op==){

            scanf("%d%d",&l,&r);

            for(int i=l;i<=r;i++)a[i]=;

        }

        else if(op==){

            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

            int cnt=;

            for(int i=l1;i<=r1;i++){

                cnt+=a[i];

                a[i]=;

            }

            for(int i=l2;i<=r2;i++){

                if(cnt==)break;

                if(a[i]==)a[i]=,cnt--;

            }

        }

        else {

            scanf("%d%d",&l,&r);

            int ans=,cnt=;

            for(int i=l;i<=r;i++){

                if(a[i]==)cnt++;

                else cnt=;

                ans=max(ans,cnt);

            }

            printf("%d\n",ans);

        }

    }

    return ;

}

50分暴力

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 200010

using namespace std;

struct node{int l,r,sum,ans,sz;}tr[*maxn];

int tag[maxn*];

void tagit(int k,int d){

    if(d==){

        tr[k].l=tr[k].r=tr[k].ans=tr[k].sz;

        tr[k].sum=;

    }

    else {

        tr[k].l=tr[k].r=tr[k].ans=;

        tr[k].sum=tr[k].sz;

    }

    tag[k]=d;

}

node update(node l,node r) {

    node ans;

    ans.l=l.l+(l.sum==?r.l:);

    ans.r=r.r+(r.sum==?l.r:);

    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]!=-) {

        int d=tag[k];

        tag[k]=-;

        tagit(k<<,d);

        tagit(k<<|,d);

    }

}

void build(int k,int l,int r){

    tr[k].l=tr[k].r=tr[k].ans=;

    tr[k].sz=tr[k].sum=r-l+;

    tag[k]=-;

    if(l==r)return;

    int mid=(l+r)>>;

    build(k<<,l,mid);build(k<<|,mid+,r);

}

void modify_0(int k,int l,int r,int opl,int opr){

    if(l>=opl&&r<=opr){

        tagit(k,);

        return;

    }

    release(k);

    int mid=(l+r)>>;

    if(opl<=mid)modify_0(k<<,l,mid,opl,opr);

    if(opr>mid)modify_0(k<<|,mid+,r,opl,opr);

    tr[k]=update(tr[k<<],tr[k<<|]);

}

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,);

            return t;

        }

        release(k);

        int mid=(l+r)>>;

        int p=modify_1(k<<,l,mid,opl,opr,i);

        if(p<i)p+=modify_1(k<<|,mid+,r,opl,opr,i-p);

        tr[k]=update(tr[k<<],tr[k<<|]);

        return p;

    }

    release(k);

    int mid=(l+r)>>,t=;

    if(opr<=mid)t=modify_1(k<<,l,mid,opl,opr,i);

    else if(opl>mid)t=modify_1(k<<|,mid+,r,opl,opr,i);

    else {

        t=modify_1(k<<,l,mid,opl,opr,i);

        if(t<i)t+=modify_1(k<<|,mid+,r,opl,opr,i-t);

    }

    tr[k]=update(tr[k<<],tr[k<<|]);

    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)>>;

    if(opr<=mid)return query(k<<,l,mid,opl,opr);

    else if(opl>mid)return query(k<<|,mid+,r,opl,opr);

    else return update(query(k<<,l,mid,opl,opr),query(k<<|,mid+,r,opl,opr));

}

int main(){

    freopen("Cola.txt","r",stdin);

    int n,m;

    scanf("%d%d",&n,&m);

    build(,,n);

    while(m--){

        int op;scanf("%d",&op);

        if(op==){

            int l,r;

            scanf("%d%d",&l,&r);

            modify_0(,,n,l,r);

        }

        else if(op==){

            int l0,r0,l1,r1;

            scanf("%d%d%d%d",&l0,&r0,&l1,&r1);

            node x=query(,,n,l0,r0);

            modify_0(,,n,l0,r0);

            if(x.sum)modify_1(,,n,l1,r1,x.sum);

        }

        else {

            int l,r;

            scanf("%d%d",&l,&r);

            node x=query(,,n,l,r);

            printf("%d\n",x.ans);

        }

    }

    return ;

}

100分线段树

秒客网

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