全村最好的嘤嘤刀

题目背景

重阳节到了，我们最好的八重樱拥有全村最好的嘤嘤刀……

题目描述

在绯玉丸力量的影响下，八重村成了一条长度为 $n$ 的八重街，并且绯玉丸可以带着八重樱出现在街上的任意地点。而我们的八重樱则会在街上任意穿梭来获取某一地点上的嘤嘤嘤能量，用以升级她的嘤嘤刀。

出题人：March_H

在每个时刻，都会发生以下 $3$ 个事件：

$1$ $x$ $val$ 表示在 $x$ 地点出现了携带着 $val$ 点嘤嘤嘤能量的绯狱丸，并且绯狱丸会吞噬该点的嘤嘤嘤能量，使得该点的嘤嘤嘤能量变为 $val - a_i$ 点， $a_i$ 为出现绯狱丸的前一刻，该点所存在的嘤嘤嘤能量。

$2$ $l$ $r$ 表示绯玉丸会带着八重樱出现在[ $l$ , $r$ ]间的任意一点。八重樱为了尽快升级她的嘤嘤刀，会获取该区间上最大的嘤嘤嘤能量。特殊的，为了保卫八重村，当 $l$ , $r$ 之间存在绯狱丸时，八重樱会优先用她的嘤嘤刀对付绯狱丸，并获得绯狱丸此时拥有的 $a_i$ 点嘤嘤嘤能量。

$3$ $l$ $r$ $val$ 绯玉丸会嘤嘤嘤，使得[ $l$ , $r$ ]上的每一个地点的嘤嘤嘤能量增加 $val$ 点(包括绯狱丸)。

输入格式

第一行为 $2$ 个数 $n$ , $m$ 。

第二行为 $n$ 个数，分别表示八重街上每个地点的初始嘤嘤嘤能量。

接下来 $m$ 行，每行会发生 $3$ 个事件中的一个，输入格式为题目描述中的格式。

输出格式

对于每一个事件 $2$ ，你应当输出八重樱在该事件中获取的嘤嘤嘤能量并换行。

当所有事件结束时，如果嘤嘤刀积累的能量小于 $10000$ ，你应当输出 $QAQ$ 。

如果在[ $10000$ , $10000000$ )间，你应当输出 $Sakura$ 。

如果都不符合，请输出 $ice$ 。

样例 #1

样例输入 #1

10 10
1 2 3 4 5 6 7 8 9 10
2 1 10
2 1 10
2 1 10
2 1 10
2 1 10
2 1 10
2 1 10
2 1 10
2 1 10
2 1 10

样例输出 #1

样例 #2

样例输入 #2

10 11
0 0 0 0 0 0 0 0 0 0
3 1 10 1
3 2 10 1
3 3 10 1
3 4 10 1
3 5 10 1
3 6 10 1
3 7 10 1
3 8 10 1
3 9 10 1
3 10 10 1
2 1 10

样例输出 #2

10
QAQ

样例 #3

样例输入 #3

10 13
0 0 0 0 0 0 0 0 0 0
1 10 10000
1 9 9000
1 8 8000
1 7 7000
1 6 6000
1 5 5000
1 4 4000
1 3 3000
1 2 2000
1 1 1000
2 10 10
2 8 8
2 8 10

样例输出 #3

10000
8000
9000
Sakura

提示

对于所有的数据：

最终答案都会在 $[0,2^{31}-1]$ 范围内；

$n$ , $m$ $\leqslant$ $100000$ 。

值得注意的是，无论八重樱是获取了某一地点的嘤嘤嘤能量还是击败了某一地点的绯狱丸，该地点的嘤嘤嘤值都应当清零而不是保留原来的数值。

对于事件 $2$ ，题目保证每个事件中最多出现 $1$ 只绯狱丸。如果出现多个最大值，在每次比较时，请选择靠右的(std默认的)。

#include<bits/stdc++.h>
#define int long long
#define PP pair <long long, long long>
using namespace std;
const int N = 1e5 + 10;
struct SegmentTree {
	int Max, l, r, lazy, Max_p;
	bool f;
} tree[N * 4];
int n, a[N], T;
int ans_yyy;
void build (int p, int l, int r) {
	tree[p].l = l, tree[p].r = r, tree[p].f = false;
	if (l == r) {
		tree[p].Max = a[l];
		tree[p].Max_p = l;
		return;
	}
	int mid = (l + r) >> 1;
	build (p * 2, l, mid);
	build (p * 2 + 1, mid + 1, r);
	if (tree[p * 2].Max > tree[p * 2 + 1].Max) tree[p].Max = tree[p * 2].Max, tree[p].Max_p = tree[p * 2].Max_p;
	else tree[p].Max = tree[p * 2 + 1].Max, tree[p].Max_p = tree[p * 2 + 1].Max_p;
}
inline void down (int p) {
	if (tree[p].lazy != 0) {
		tree[p * 2].Max += tree[p].lazy;
		tree[p * 2 + 1].Max += tree[p].lazy;
		tree[p * 2].lazy += tree[p].lazy;
		tree[p * 2 + 1].lazy += tree[p].lazy;
		tree[p].lazy = 0;
	}
	if (tree[p].f != false) {
		tree[p * 2].Max = 0;
		tree[p * 2 + 1].Max = 0;
		tree[p * 2].f = true;
		tree[p * 2 + 1].f = true;
		tree[p].f = false;
	}
}
void change_1 (int p, int l, int r, int z) {
	if (tree[p].l == l && tree[p].r == r) {
		int num = z - tree[p].Max;
		tree[p].Max = num;
		tree[p].lazy = num;
		return;
	}
	down (p);
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) change_1 (p * 2, l, r, z);
	if (mid < r) change_1 (p * 2 + 1, l, r, z);
	if (tree[p * 2].Max > tree[p * 2 + 1].Max) tree[p].Max = tree[p * 2].Max, tree[p].Max_p = tree[p * 2].Max_p;
	else tree[p].Max = tree[p * 2 + 1].Max, tree[p].Max_p = tree[p * 2 + 1].Max_p;
}
void change_2 (int p, int l, int r, int z) {
	if (tree[p].l == l && tree[p].r == r) {
		tree[p].Max = z;
		tree[p].lazy = z;
		tree[p].f = true;
		return;
	}
	down (p);
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) change_2 (p * 2, l, r, z);
	if (mid < r) change_2 (p * 2 + 1, l, r, z);
	if (tree[p * 2].Max > tree[p * 2 + 1].Max) tree[p].Max = tree[p * 2].Max, tree[p].Max_p = tree[p * 2].Max_p;
	else tree[p].Max = tree[p * 2 + 1].Max, tree[p].Max_p = tree[p * 2 + 1].Max_p;
}
void change_3 (int p, int l, int r, int z) {
	if (tree[p].l >= l && tree[p].r <= r) {
		tree[p].Max += z;
		tree[p].lazy += z;
		return;
	}
	down (p);
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) change_3 (p * 2, l, r, z);
	if (mid < r) change_3 (p * 2 + 1, l, r, z);
	if (tree[p * 2].Max > tree[p * 2 + 1].Max) tree[p].Max = tree[p * 2].Max, tree[p].Max_p = tree[p * 2].Max_p;
	else tree[p].Max = tree[p * 2 + 1].Max, tree[p].Max_p = tree[p * 2 + 1].Max_p;
}
PP query (int p, int l, int r) {
	if (tree[p].l >= l && tree[p].r <= r) return {tree[p].Max, tree[p].Max_p};
	int mid = (tree[p].l + tree[p].r) >> 1;
	down (p);
	PP res = {-1, 0};
	if (l <= mid) {
		PP o = query (p * 2, l, r);
		if (o.first > res.first || (o.first == res.first && o.second > res.second)) res = o;
	}
	if (mid < r) {
		PP o = query (p * 2 + 1, l, r);
		if (o.first > res.first || (o.first == res.first && o.second > res.second)) res = o;
	}
	return res;
}
signed main () {
	ios::sync_with_stdio (false);
	cin.tie (0), cout.tie (0);
	cin >> n >> T;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	build (1, 1, n);
	while (T -- ) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, z;
			cin >> x >> z;
			change_1 (1, x, x, z);
		}
		if (op == 2) {
			int l, r;
			cin >> l >> r;
			PP ans = query (1, l, r);
			cout << ans.first << endl;
			ans_yyy += ans.first;
			change_2 (1, ans.second, ans.second, 0);
		}
		if (op == 3) {
			int l, r, z;
			cin >> l >> r >> z;
			change_3 (1, l, r, z);
		}
	}
	if (ans_yyy < 10000) cout << "QAQ" << endl;
	else if (ans_yyy >= 10000 && ans_yyy < 10000000) cout << "Sakura" << endl;
	else cout << "ice" << endl;
	return 0;
}
/*
10 10
1 2 3 4 5 6 7 8 9 10
1 1 114514
2 1 1
2 1 1
2 2 2
2 2 2
3 1 2 5
2 1 1
2 1 1
2 2 2
2 2 2

*/

2022/7/13 18:17