SHOI2015 脑洞治疗仪（线段树）

发表于 |
字数统计: 1,600字 | 阅读时长 ≈ 8min
问题描述

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

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

1010001110

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

例如，用上面第 $8$ 号位置到第 $10$ 号位置去修补第 $1$ 号位置到第 $4$ 号位置的脑洞，我们就会得到：

1111001000

如果再用第 $1$ 号位置到第 $4$ 号位置去修补第 $8$ 号位置到第 $10$ 号位置：

0000001111

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

如果再用第 $7$ 号位置到第 $10$ 号位置去填补第 $1$ 号位置到第 $6$ 号位置：

1111000000

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

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

输入格式

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

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

  • $0\quad l\quad r$：SHTSC 挖了一个范围为 $[l, r]$ 的脑洞。
  • $1\quad l_0\quad r_0\quad l_1\quad r_1$：SHTSC 进行了一次脑洞治疗，用从 $l_0$ 到 $r_0$ 的脑组织修补 $l_1$ 到 $r_1$ 的脑洞。
  • $2\quad l\quad r$：SHTSC 询问 $[l, r]$ 区间内最大的脑洞有多大。

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

输出格式

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

样例输入
1
2
3
4
5
6
7
8
9
10
11
10 10
0 2 2
0 4 6
0 10 10
2 1 10
1 8 10 1 4
2 1 10
1 1 4 8 10
2 1 10
1 7 10 1 6
2 1 10
样例输出
1
2
3
4
3
3
6
6
提示

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

唯一特殊的操作就是治疗操作，但是容易发现，只需要先查询 $[l_0,r_0]$ 的脑组织数量，填的时候就是先填左边，再填右边，如果当前区间能填完，就打个区间覆盖标记然后返回，或者脑组织填完了也返回，容易发现这样复杂度就是一个 $\log $ 的了

剩下的就只需要写一个维护区间最大连续0的线段树就好了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int _R()
{
    char t=GC;int x=0;
    while(t<48||t>57)t=GC;
    for(;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
    return x;
}
int n,m;
struct data{int Lmax,Rmax,Max,sum,len;};
data operator+(data a,data b)
{
    data c=(data){0,0,0,0};
    if(a.sum==a.len)c.Lmax=a.len+b.Lmax;
    else c.Lmax=a.Lmax;
    if(b.sum==b.len)c.Rmax=b.len+a.Rmax;
    else c.Rmax=b.Rmax;
    c.Max=max(max(a.Max,b.Max),a.Rmax+b.Lmax);
    c.sum=a.sum+b.sum;
    c.len=a.len+b.len;
    return c;
}
struct node
{
    node *ls,*rs;
    data v;int lazy;
}seg[N<<1],*rt,*tl,*null;
void Init()
{
    rt=tl=null=seg;null->lazy=-1;
    null->ls=null->rs=null;
}
void build(node *&p,int l,int r)
{
    p=++tl;p->lazy=-1;
    p->ls=p->rs=null;
    if(l==r){p->v=(data){0,0,0,0,1};return;}
    int mid=l+r>>1;
    build(p->ls,l,mid);
    build(p->rs,mid+1,r);
    p->v=p->ls->v+p->rs->v;
}
void putdown(node *p)
{
    node *l=p->ls,*r=p->rs;
    l->lazy=r->lazy=p->lazy;
    int dl=l->v.len,dr=r->v.len;
    if(p->lazy==1)
    {
        l->v=(data){0,0,0,0,dl};
        r->v=(data){0,0,0,0,dr};
    }
    else
    {
        l->v=(data){dl,dl,dl,dl,dl};
        r->v=(data){dr,dr,dr,dr,dr};
    }
    p->lazy=-1;
}
void cover(node *p,int l,int r,int x,int y)
{
    if(p->lazy!=-1)putdown(p);
    if(x<=l&&y>=r)
    {
        int d=p->v.len;
        p->v=(data){d,d,d,d,d};
        p->lazy=0;return;
    }
    int mid=l+r>>1;
    if(x<=mid)cover(p->ls,l,mid,x,y);
    if(y>mid)cover(p->rs,mid+1,r,x,y);
    p->v=p->ls->v+p->rs->v;
}
int repair(node *p,int l,int r,int x,int y,int d)
{
    if(p->lazy!=-1)putdown(p);
    if(d==0)return 0;
    if(x<=l&&y>=r&&d>=p->v.sum)
    {
        int d=p->v.sum;
        p->v=(data){0,0,0,0,r-l+1};
        p->lazy=1;return d;
    }
    int mid=l+r>>1,sum=0;
    if(x<=mid)sum+=repair(p->ls,l,mid,x,y,d);
    if(y>mid)sum+=repair(p->rs,mid+1,r,x,y,d-sum);
    p->v=p->ls->v+p->rs->v;
    return sum;
}
int getsum(node *p,int l,int r,int x,int y)
{
    if(p->lazy!=-1)putdown(p);
    if(x<=l&&y>=r)return p->v.sum;
    int mid=l+r>>1,sum=0;
    if(x<=mid)sum+=getsum(p->ls,l,mid,x,y);
    if(y>mid)sum+=getsum(p->rs,mid+1,r,x,y);
    return sum;
}
data getmax(node *p,int l,int r,int x,int y)
{
    if(p->lazy!=-1)putdown(p);
    if(x<=l&&y>=r)return p->v;
    int mid=l+r>>1;
    if(x>mid)return getmax(p->rs,mid+1,r,x,y);
    if(y<=mid)return getmax(p->ls,l,mid,x,y);
    return getmax(p->ls,l,mid,x,y)+getmax(p->rs,mid+1,r,x,y);
}
int main()
{
    int i,j,k,x,y,a,b;
    n=_R();m=_R();
    Init();build(rt,1,n);
    for(i=1;i<=m;i++)
    {
        k=_R();x=_R();y=_R();
        if(k==0)cover(rt,1,n,x,y);
        if(k==1)
        {
            a=_R();b=_R();
            j=y-x+1-getsum(rt,1,n,x,y);
            cover(rt,1,n,x,y);
            repair(rt,1,n,a,b,j);
        }
        if(k==2)printf("%d\n",getmax(rt,1,n,x,y).Max);
    }
}