Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P7447 [Ynoi2007] rgxsxrs

Posted on Edited on

毒瘤的出题人，怪物一样的题目。

题目简介

维护一个序列，执行一下操作：

  • $1 \ l \ r \ x$：表示将区间 $[l,r]$ 中所有 $>x$ 的元素减去 $x$。

  • $2 \ l \ r$：表示询问区间 $[l,r]$ 的和，最小值，最大值。

没了，就没了（人没了）。

数据范围：对于 $100%$ 的数据，$n,m≤5×10^5，1≤a_i,x≤10^9$ 。

时间：$3.00s$ ~ $6.00s$。

空间：$64.00MB$

Solution

观察题面，数据范围，时空限制，然后我们可以（放弃）联想到区间的最大值一定不会变化，在和传说中的第二分块联想了一下，可以联想到值域分块，然而值域过于巨大，我们考虑再次将值域细化成：$B^{i-1}-B^i$ ，这样的话我们发现如果最小值 $\ge$ $x$，打上标记然后返回，最大值 $\le$ $x$ 直接跳过，然后就到了最关键的最大值 $\ge$ x $\ge$ 最小值的时候。

仔细思考这一步应该怎么处理，如果使用普通线段树的话，时间必定爆炸，于是考虑二次分块，首先分块数列，然后再在每一块中建立一颗值域线段树，在线段树中执行上述操作。

设上述块的数量为 $cnt$，特殊情况的块长为 $len$，故在值域线段树中最多每次执行$ \frac {len}{x}$次操作，那么最后就要使$\frac{len}{x} * cnt$最小，当 $x$ 很大时我们可以发现没有多少数比它大，当 $x$ 很小的时候我们同理可以发现没有多少数比他小，故我们需要特殊考虑的就是刚好卡在中间的数，此时令$\frac{len}{x} = B$，此时$cnt = \log _{B}{10^9}$时，此时的时间复杂度可以证明当$B = 16$时最小为 $O((n+m) × \log _{B}{10^9} × \log n + n × B × \log n× \log _B 10^9)$。

然而你打完一交，$MLE$ 了，再次考虑优化，因为线段树的空间随层数的递增而成倍增长，所以重点放在优化叶子节点，我们不妨设置一个数 $limit$ ，让线段树 $\le \ limit$ 的区间直接暴力（底层分块：底层暴力分块）， 理论上 $limit = 4$ 时最优。

代码

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#include<bits/stdc++.h>
#define LL long long
#define l(x) x << 1
#define r(x) x << 1 | 1
using namespace std;
const int N = 5e5 + 5;
const int B = 32, mod = 1 << 20;
const int limit = 40; // 事实上40更优秀
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || c > '9'){if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res;
}
struct segment{ // 线段树的底层 
	int l, r;
	bool flag;
}tree[N / limit << 4];
int n, m;
int a[N];
int now[N];
int bet[N];
int minn, maxn;
int tot;
LL sum;
int down[N];
struct Tree{ // 分块 
	LL l, r;
	int id;
	struct Node{ // 建树
		int minn = 2147483647, maxn, cnt;
		LL add, sum;
	}tr[N / limit << 2];
	void change(int x)
	{
		tr[x].sum = tr[x].cnt = tr[x].maxn = 0, tr[x].minn = 2147483647;
		for(int i = tree[x].l;i <= tree[x].r; i ++)
		{
			if(bet[i] == id)
			{
				tr[x].cnt ++;
				tr[x].sum += a[i];
				tr[x].minn = min(tr[x].minn, a[i]);
				tr[x].maxn = max(tr[x].maxn, a[i]);
			}
		}
	}
	inline void pushup(int x) 
	{
		if(tree[x].flag) change(x); // 小于就暴力
		else{
			tr[x].sum = tr[l(x)].sum + tr[r(x)].sum;
			tr[x].cnt = tr[l(x)].cnt + tr[r(x)].cnt;
			tr[x].minn = min(tr[l(x)].minn, tr[r(x)].minn);
			tr[x].maxn = max(tr[l(x)].maxn, tr[r(x)].maxn);
		}
	}
	inline void addage(int x, int y) // 将y下传给x
	{
		tr[x].sum += tr[x].cnt * tr[y].add;
		tr[x].add += tr[y].add;
		tr[x].minn += tr[y].add;
		tr[x].maxn += tr[y].add;
	}
	inline void pushdown(int x)
	{
		if(!tr[x].add) return ;
		if(tree[x].flag)
		{
			for(int i = tree[x].l;i <= tree[x].r;i ++)
			{
				if(bet[i] == id) a[i] += tr[x].add;
			}
		}
		else addage(l(x), x), addage(r(x), x);
		tr[x].add = 0;
	}
	void change_all(int x)
	{
		if(x > 1) change_all(x >> 1);
		pushdown(x);
	}
	void modify(int x)
	{
		int val = a[x];
		change_all(now[x]);
		a[x] = val;
		x = now[x];
		pushup(x);
		for(x >>= 1; x;x >>= 1) pushup(x);
	}
	void ask(int x, int l, int r)
	{
		if(l <= tree[x].l && tree[x].r <= r)
		{
			minn = min(minn, tr[x].minn);
			maxn = max(maxn, tr[x].maxn);
			sum += tr[x].sum;
			return ;
		}
		pushdown(x);
		if(tree[x].flag)
		{
			for(int i = tree[x].l;i <= tree[x].r;i ++)
			{
				if(i >= l && i <= r && bet[i] == id)
				{
					minn = min(minn, a[i]);
					maxn = max(maxn, a[i]);
					sum += a[i];
				}
			}
			return ;
		}
		if(tree[l(x)].r >= l) ask(x << 1, l, r);
		if(tree[r(x)].l <= r) ask(x << 1 | 1, l, r);
	}
	void modify(int x, int l, int r, LL w)
	{
		if(tr[x].maxn <= w) return ;
		if(tree[x].l >= l && tree[x].r <= r)
		{
			if(tr[x].minn > w)
			{
				tr[x].add -= w;
				tr[x].maxn -= w;
				tr[x].minn -= w;
				tr[x].sum -= tr[x].cnt * w;
				return ;
			}
			pushdown(x);
			if(tree[x].flag)
			{
				for(int i = tree[x].l;i <= tree[x].r;i ++)
				{
					if(bet[i] == id) a[i] -= (a[i] > w) * w;
				}
				pushup(x);
			}
			modify(l(x), l, r, w), modify(r(x), l, r, w);
			pushup(x);
			return ;
		}
		pushdown(x);
		if(tree[x].flag)
		{
			for(int i = tree[x].l;i <= tree[x].r;i ++)
			{
				if(l <= i && i <= r && bet[i] == id) a[i] -= (a[i] > w) * w;
			}
			pushup(x);
			return ;
		}
		if(tree[l(x)].r >= l) modify(l(x), l, r, w);
		if(tree[r(x)].l <= r) modify(r(x), l, r, w);
		pushup(x);
	}
	void del(int x)
	{
		if(tr[x].minn >= l) return ;
		pushdown(x);
		if(tree[x].flag)
		{
			tr[x].sum = tr[x].cnt = tr[x].maxn = 0, tr[x].minn = 2147483647;
			for(int i = tree[x].l;i <= tree[x].r;i ++)
			{
				if(bet[i] == id)
				{
					if(a[i] >= l)
					{
						tr[x].cnt ++;
						tr[x].sum += a[i];
						tr[x].maxn = max(tr[x].maxn, a[i]);
						tr[x].minn = min(tr[x].minn, a[i]);
					}
					else down[++ tot] = i, bet[i] = 0;
				}
			}
			return ;
		}
		del(l(x)), del(r(x));
		pushup(x);
	}
}seg[8];
int cnt;
void add(int x)
{
	for(int i = 1;;i ++)
	{
		if(seg[i].l <= a[x] && seg[i].r >= a[x])
		{
			bet[x] = i, seg[i].modify(x);
			break;
		}
	}
}
void build(int x, int l, int r)
{
	tree[x].l = l, tree[x].r = r;
	if(r - l > limit)
	{
		int mid = l + r >> 1;
		build(x << 1, l, mid);
		build(x << 1 | 1, mid + 1, r);
		return ;
	}
	tree[x].flag = 1;
	for(;l <= r;l ++) now[l] = x;
}
void ask(int l, int r)
{
	minn = 2147483647, maxn = sum = 0;
	for(int i = 1;i <= cnt;i ++)
		seg[i].ask(1, l, r);
}
void add(int l, int r, int w)
{
	for(int i = 1;i <= cnt;i ++)
	{
		seg[i].modify(1, l, r, w);
		seg[i].del(1);
	}
	for(;tot;tot --) add(down[tot]);
}
int last;
int main()
{
	read(n), read(m);
	for(int i = 1;i <= n;i ++) read(a[i]);
	build(1, 1, n);
	for(LL j = 1;;j *= B)// 初始化
	{
		seg[++ cnt].l = j;
		seg[cnt].id = cnt;
		seg[cnt].r = j * B - 1;
		if(seg[cnt].r >= 1e9) break;
	}
	for(int i = 1;i <= n;i ++) add(i);
	int op, l, r, w;
	while(m --)
	{
		read(op), read(l), read(r);
		if(op == 1)
		{
			read(w);
			l ^= last, r ^= last, w ^= last;
			// if(l > r) swap(l, r);
			add(l, r, w);
		}
		if(op == 2)
		{
			l ^= last, r ^= last;
			// if(l > r) swap(l, r); // 出题人较为良心
			ask(l, r);
			last = sum % mod;
			printf("%lld %d %d\n", sum, minn, maxn);
		}
	}
	return 0;
}