libreoj 2037 洛谷 4344 [SHOI2015]脑洞治疗仪 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1.6k 字 | 阅读时长 ≈ 7 分钟

前言

友链：zhk 的题解

但是我觉得他这篇里面提的有点简单（主要是没给代码），于是我自己来写一下~

题意简述

zps 是又可爱又傻的女孩子！于是她决定自己治疗她的脑子

zps 的垃圾脑子是一个长度为 $n$ 的序列，每个位置用 $1$ 表示这里有脑组织，$0$ 表示有脑洞（没有脑组织）。初始时全部正常。支持操作若干：

0 l r zps 在 $[l,r]$ 之间所有脑组织都挖掉

1 l0 r0 l1 r1 zps 把 $[l_0,r_0]$ 中的脑组织都挖出来，假设有 $K$ 个，那么她会用这些脑洞来填补 $[l_1,r_1]$ 中从左到右前 $K$ 个脑洞。如果还有剩下的脑组织，她会选择直接扔掉

3 l r 询问区间 $[l,r]$ 中，最长连续脑洞长度。

$1\le n,m\le 2\times 10^5$

思路框架

线段树维护。我们整理一下需要哪些操作。

对于 $0$ 操作，我们需要区间覆盖操作

对于 $1$ 操作，我们需要求出 $[l_0,r_0]$ 中的脑洞个数 $K$（即维护区间和 $S$），把这一段区间全都覆盖为 $0$，然后还要把 $l_1,r_1$ 的前 $k$ 个脑洞变成脑组织。

对于 $2$ 操作，我们要支持维护区间的最大连续长度操作。

查询

要维护区间脑洞个数 $S$，然后要维护最长左连续脑洞长度 $LC$，右连续脑洞长度 $RC$，还有一个最长连续脑洞长度 $X$。

$S$ 就是左右加起来，显然。

如果左儿子的 $LC$ 等于左儿子的长度，那么我们的 $LC$ 跨过整个左半边再加上右儿子的 $LC$。否则 $LC$ 等于左儿子的 $LC$。

$RC$ 和 $LC$ 类似的，就是判一下能不能跨过整个右半边。

$X$ 就等于左右儿子 $X$ 的最大值，再和 左 $RC$ 加上右 $LC$ 取 $\max$。

我们把每个线段树节点封装成一个 struct，然后重载运算符来实现这个合并。

修改

区间覆盖

我们打一个 $C$ 标记 （C=Cover）。然后每次我们先打一下 $C$ 标记，然后如果覆盖的是 $0$（脑洞），$S=LC=RC=X=R-L+1$。否则 $S=LC=RC=X=0$。

区间填充前 k 个

把区间分成左右两块，设左半边的脑洞个数为 $lson$。

如果 $k<=lson$，那么只在左边填即可。

否则我们就把左半区间整个覆盖上 $1$ （脑组织），然后在右半边填充 $k-lson$ 个。

线段树上查找的边界为，当：

  1. 当前区间完全被查询区间覆盖
  2. （且）$k>=S$

（这种情况显然是直接整个区间覆盖上 $1$ 就行了）

为了方便写代码，我们填充完 一段区间后，函数返回一个整数，表示成功填充了多少个。 （就是有多少挖出来的脑组织没有被扔掉）。后面就会知道它为啥好写了。

代码

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
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 255555
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int R()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=R();}
	    va_end(args);
	}
	struct node{int l,r,lc,rc,s,x,c;} ;
	node operator+(node ls,node rs) // 重载一个加号~
	{
		node t;
		t.l=ls.l; t.r=rs.r; t.c=-1;
		t.s=ls.s+rs.s;
		t.x=max(max(ls.x,rs.x),ls.rc+rs.lc);
		t.lc=ls.lc; if (ls.lc==ls.r-ls.l+1) t.lc+=rs.lc;
		t.rc=rs.rc; if (rs.rc==rs.r-rs.l+1) t.rc+=ls.rc;
		return t;
	}
	class SegementTree
	{
	public:
		node tree[N<<2];
		#define ls index<<1
		#define rs index<<1|1

		#define L  tree[index].l
		#define R  tree[index].r
		#define LC tree[index].lc
		#define RC tree[index].rc
		#define S  tree[index].s
		#define X  tree[index].x
		#define C  tree[index].c
		void Update(int index=1) {tree[index]=tree[ls]+tree[rs];}
		void Build(int l,int r,int index=1) // 常规的建树
		{
			L=l,R=r;
			if (l==r) {S=X=LC=RC=0; return;}
			// 一开始都是脑组织，所以脑洞数量为 0
			int mid=(l+r)>>1;
			Build(l,mid,ls); Build(mid+1,r,rs);
			Update(index); 
		}
		void CoverOne(int x,int index=1)
		{
			C=x;
			if (x==1) {S=X=LC=RC=0;}
			else 	  {S=X=LC=RC=R-L+1;}
		}
		void PushDown(int index=1)
		{
			if (~C)
			{
				CoverOne(C,ls); CoverOne(C,rs);
				C=-1;
			}
		}
		void Cover(int l,int r,int x,int index=1) // 区间覆盖操作
		{
			if (l>R or L>r) return;
			if (l<=L and R<=r) return CoverOne(x,index);
			PushDown(index);
			Cover(l,r,x,ls); Cover(l,r,x,rs);
			Update(index);
		}
		int Fill(int l,int r,int cnt,int index=1) // 区间填充操作
		{
			if (l<=L and R<=r and cnt>=S) 
			{
				int s=S;
				CoverOne(1,index);
				return s;
			}

			PushDown(index);
			int mid=(L+R)>>1; int sum=0;
			if (r<=mid) sum=Fill(l,r,cnt,ls);
			else if (l>mid) sum=Fill(l,r,cnt,rs);
			else
			{
				sum=Fill(l,mid,cnt,ls); 
				if (cnt>sum) sum+=Fill(mid+1,r,cnt-sum,rs);
			}
			Update(index);
			return sum;
		}
		node Query(int l,int r,int index=1)
		{
			if (l<=L and R<=r) return tree[index];
			PushDown(index);
			int mid=(L+R)>>1;
			if (r<=mid) return Query(l,r,ls);
			else if (l>mid) return Query(l,r,rs);
			else return Query(l,mid,ls)+Query(mid+1,r,rs);
		}
	}T;

	int n,q;
	void Input()
	{
		Rd(2,&n,&q);
		T.Build(1,n);
	}
	void Soviet()
	{
		F(i,1,q)
		{
			int o,l,r; Rd(3,&o,&l,&r);
			if (o==0)
			{
				T.Cover(l,r,0);
			}
			if (o==1)
			{
				int l2,r2; Rd(2,&l2,&r2);
				int cnt=(r-l+1)-T.Query(l,r).s;
				T.Cover(l,r,0);
				if (cnt>0) T.Fill(l2,r2,cnt);
			}
			if (o==2)
			{
				printf("%d\n",T.Query(l,r).x);
			}
		}
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w