bzoj4592 [Shoi2015]脑洞治疗仪

Description

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

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

1 0 1 0 0 0 1 1 1 0

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

（所以脑洞治疗仪是脑洞的治疗仪？）

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

1 1 1 1 0 0 1 0 0 0

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

0 0 0 0 0 0 1 1 1 1

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

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

1 1 1 1 0 0 0 0 0 0

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

假定初始时SHTSC并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答SHTSC的问题：

在大脑某个区间中最大的连续脑洞区域有多大。

Input

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

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

0 l r ：SHTSC挖了一个从l到r的脑洞。

1 l0 r0 l1 r2 ：SHTSC进行了一次脑洞治疗，用从l0到r0的脑组织修补l1到r1的脑洞。

2 l r ：SHTSC询问l到r这段区间最大的脑洞有多大。

n,m <=200000，1<=l<=r<=n

Output

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

Sample Input

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

Sample Output

3
3
6
6

正解：线段树。

赤裸裸的线段树，没什么要多说的。。注意填补脑洞的时候要二分一下右端点。

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <cstdio>
  7 #include <vector>
  8 #include <cmath>
  9 #include <queue>
 10 #include <stack>
 11 #include <map>
 12 #include <set>
 13 #define N (300010)
 14 #define ls (x<<1)
 15 #define rs (x<<1|1)
 16 #define il inline
 17 #define RG register
 18 #define ll long long
 19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 20 
 21 using namespace std;
 22 
 23 struct data{ int res,LL,RR; };
 24 
 25 int lazy[4*N],sum[4*N],res[4*N],LL[4*N],RR[4*N],n,m,l,r,L,R,op;
 26 
 27 il int gi(){
 28     RG int x=0,q=1; RG char ch=getchar();
 29     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 30     if (ch=='-') q=-1,ch=getchar();
 31     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
 32     return q*x;
 33 }
 34 
 35 il void pushup(RG int x,RG int l,RG int r){
 36     sum[x]=sum[ls]+sum[rs]; RG int mid=(l+r)>>1;
 37     res[x]=max(RR[ls]+LL[rs],max(res[ls],res[rs]));
 38     LL[x]=(res[ls]==mid-l+1) ? res[ls]+LL[rs] : LL[ls];
 39     RR[x]=(res[rs]==r-mid) ? res[rs]+RR[ls] : RR[rs]; return;
 40 }
 41 
 42 il void pushdown(RG int x,RG int l,RG int r){
 43     RG int mid=(l+r)>>1;
 44     sum[ls]=res[ls]=LL[ls]=RR[ls]=(mid-l+1)*lazy[x];
 45     sum[rs]=res[rs]=LL[rs]=RR[rs]=(r-mid)*lazy[x];
 46     lazy[ls]=lazy[x],lazy[rs]=lazy[x],lazy[x]=-1; return;
 47 }
 48 
 49 il void build(RG int x,RG int l,RG int r){
 50     lazy[x]=-1; if (l==r) return; RG int mid=(l+r)>>1;
 51     build(ls,l,mid),build(rs,mid+1,r),pushup(x,l,r); return;
 52 }
 53 
 54 il void update(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int v){
 55     if (xl<=l && r<=xr){ sum[x]=res[x]=LL[x]=RR[x]=(r-l+1)*v,lazy[x]=v; return; }
 56     if (lazy[x]!=-1) pushdown(x,l,r); RG int mid=(l+r)>>1;
 57     if (xr<=mid) update(ls,l,mid,xl,xr,v);
 58     else if (xl>mid) update(rs,mid+1,r,xl,xr,v);
 59     else update(ls,l,mid,xl,mid,v),update(rs,mid+1,r,mid+1,xr,v);
 60     pushup(x,l,r); return;
 61 }
 62 
 63 il int query(RG int x,RG int l,RG int r,RG int xl,RG int xr){
 64     if (xl<=l && r<=xr) return sum[x];
 65     if (lazy[x]!=-1) pushdown(x,l,r); RG int mid=(l+r)>>1;
 66     if (xr<=mid) return query(ls,l,mid,xl,xr);
 67     else if (xl>mid) return query(rs,mid+1,r,xl,xr);
 68     else return query(ls,l,mid,xl,mid)+query(rs,mid+1,r,mid+1,xr);
 69 }
 70 
 71 il data getans(RG int x,RG int l,RG int r,RG int xl,RG int xr){
 72     if (xl<=l && r<=xr) return (data){res[x],LL[x],RR[x]};
 73     if (lazy[x]!=-1) pushdown(x,l,r); RG int mid=(l+r)>>1;
 74     if (xr<=mid) return getans(ls,l,mid,xl,xr);
 75     else if (xl>mid) return getans(rs,mid+1,r,xl,xr);
 76     else{
 77     RG data res,res1=getans(ls,l,mid,xl,mid),res2=getans(rs,mid+1,r,mid+1,xr);
 78     res.res=max(res1.RR+res2.LL,max(res1.res,res2.res));
 79     res.LL=(res1.res==mid-xl+1) ? res1.res+res2.LL : res1.LL;
 80     res.RR=(res2.res==xr-mid) ? res2.res+res1.RR : res2.RR; return res;
 81     }
 82 }
 83 
 84 il void work(){
 85     n=gi(),m=gi(),build(1,1,n);
 86     for (RG int i=1;i<=m;++i){
 87     op=gi(); if (!op) l=gi(),r=gi(),update(1,1,n,l,r,1);
 88     if (op==1){
 89         l=gi(),r=gi(),L=gi(),R=gi();
 90         RG int res=r-l+1-query(1,1,n,l,r); update(1,1,n,l,r,1);
 91         if (res>=query(1,1,n,L,R)) update(1,1,n,L,R,0); else{
 92         RG int h=L,t=R,mid,ans=L-1;
 93         while (h<=t){
 94             mid=(h+t)>>1;
 95             if (query(1,1,n,L,mid)<=res) ans=mid,h=mid+1;
 96             else t=mid-1;
 97         }
 98         if (L<=ans) update(1,1,n,L,ans,0);
 99         }
100     }
101     if (op==2){
102         l=gi(),r=gi();
103         RG data res=getans(1,1,n,l,r);
104         printf("%d
",res.res);
105     }
106     }
107     return;
108 }
109 
110 int main(){
111     File("hole");
112     work();
113     return 0;
114 }