bzoj 4592 脑洞治疗仪

Posted on | Views:

线段树.

  • 需要维护一段区间的区间和,最长包含左端点的全 $0$ 区间长度,最长的包含右端点的全 $0$ 区间长度,最长全 $0$ 区间长度,以及支持区间赋值.
  • 用线段树维护.操作 $1,3$ 都比较简单,操作 $2$ ,先查询 $[L_0,R_0]$ 中 $1$ 的数目,再将这段覆盖成 $0$ .
  • 接下来用线段树把 $[L_1,R_1]$ 拆成 $\log$ 个线段树上的区间,遍历一次,找到能填补的最后一个区间.
  • 再在那个区间内二分能填到的最后一个位置.方法类似于找第 $k$ 大.这样就只有一只 $\log$ 了.
  • 时间复杂度 $O(n \cdot \log n)$ .

另外一个做法是使用珂朵莉树,但使用前提是数据随机,或者,区间赋值操作的数目与随机时的数目相近.

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,m;
struct SegTree
{
	struct node
	{
		int sum,tag,Len;
		int lenl,lenr,len;
	}Tree[MAXN<<2];	
	friend node operator + (node lson,node rson)
	{
		node root;
		root.Len=lson.Len+rson.Len;
		root.sum=lson.sum+rson.sum;
		if(lson.lenl==lson.Len)
			root.lenl=lson.lenl+rson.lenl;
		else
			root.lenl=lson.lenl;
		if(rson.lenr==rson.Len)
			root.lenr=rson.lenr+lson.lenr;
		else
			root.lenr=rson.lenr;
		root.len=max(lson.len,rson.len);
		root.len=max(root.len,lson.lenr+rson.lenl);
		root.len=max(root.len,root.lenl);
		root.len=max(root.len,root.lenr);
		return root;
	}
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		int t=root.tag;
		root=lson+rson;
		root.tag=t;
	}
	void BuildTree(int o,int l,int r)
	{
		root.sum=root.Len=r-l+1;
		root.tag=-1;
		root.lenl=root.lenr=root.len=0;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
	}
	void Modifiy(int o,int c)
	{
		root.tag=c;
		root.sum=root.Len*c;
		root.lenl=root.lenr=root.len=c?0:root.Len;
	}
	void pushdown(int o)
	{
		if(root.tag!=-1)
		{
			Modifiy(o<<1,root.tag);
			Modifiy(o<<1|1,root.tag);
			root.tag=-1;
		}
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
		{
			Modifiy(o,c);
			return;
		}
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	int query_sum(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root.sum;
		int mid=(l+r)>>1;
		pushdown(o);
		int res=0;
		if(L<=mid)
			res+=query_sum(o<<1,l,mid,L,R);
		if(R>mid)
			res+=query_sum(o<<1|1,mid+1,r,L,R);
		return res;
	}
	int tmp[50],tot,LL[50],RR[50];
	void Split(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
		{
			tmp[++tot]=o;
			LL[tot]=l;
			RR[tot]=r;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			Split(o<<1,l,mid,L,R);
		if(R>mid)
			Split(o<<1|1,mid+1,r,L,R);
	}
	int Binary_Search(int o,int l,int r,int x)
	{
		int mid=(l+r)>>1;
		if(l!=r)
			pushdown(o);
		if(root.Len-root.sum==x)
			return r;
		if(lson.Len-lson.sum<x)
			return Binary_Search(o<<1|1,mid+1,r,x-lson.Len+lson.sum);
		else
			return Binary_Search(o<<1,l,mid,x);
	}
	int Search(int L,int R,int brain)
	{
		tot=0;
		Split(1,1,n,L,R);
		int zero=0,mxrt=-1,x;
		for(int i=1;i<=tot && mxrt==-1;++i)
		{
			zero+=Tree[tmp[i]].Len-Tree[tmp[i]].sum;
			if(zero>=brain)
			{
				mxrt=i;
				x=brain-(zero-Tree[tmp[i]].Len+Tree[tmp[i]].sum);
			}	
		}
		return Binary_Search(tmp[mxrt],LL[mxrt],RR[mxrt],x);
	}
	node query_len(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root;
		int mid=(l+r)>>1;
		pushdown(o);
		if(R<=mid)
			return query_len(o<<1,l,mid,L,R);
		if(L>mid)
			return query_len(o<<1|1,mid+1,r,L,R);
		if(L<=mid && R>mid)
			return query_len(o<<1,l,mid,L,R)+query_len(o<<1|1,mid+1,r,L,R);
	}
	int solve(int L,int R)
	{
		node tmp=query_len(1,1,n,L,R);
		return tmp.len;
	}
}T;
int main()
{
	n=read(),m=read();
	T.BuildTree(1,1,n);
	while(m--)
	{
		int tp=read();
		if(tp==0)
		{
			int L=read(),R=read();
			T.upd(1,1,n,L,R,0);
		}
		else if(tp==1)
		{
			int L0=read(),R0=read();
			int L1=read(),R1=read();
			int tot1=T.query_sum(1,1,n,L0,R0);
			if(!tot1)
				continue;
			T.upd(1,1,n,L0,R0,0);
			int tot2=T.query_sum(1,1,n,L1,R1);
			if(tot1+tot2>=R1-L1+1)
				T.upd(1,1,n,L1,R1,1);
			else
			{
				int pos=T.Search(L1,R1,tot1);
				T.upd(1,1,n,L1,pos,1);
			}	
		}
		else
		{
			int L=read(),R=read();
			printf("%d\n",T.solve(L,R));
		}	
	}
	return 0;
}