社区讨论

P4970求调（调对送你个MM）

多多喝岩浆
灌水区参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo8lit96
此快照首次捕获于
2023/10/27 20:35
2 年前
此快照最后确认于
2023/10/27 20:35
2 年前
查看原帖

全村最好的嘤嘤刀

题目背景

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

题目描述

在绯玉丸力量的影响下，八重村成了一条长度为 nn 的八重街，并且绯玉丸可以带着八重樱出现在街上的任意地点。而我们的八重樱则会在街上任意穿梭来获取某一地点上的嘤嘤嘤能量，用以升级她的嘤嘤刀。
出题人：March_H
在每个时刻，都会发生以下 33 个事件：
11 xx valval 表示在 xx 地点出现了携带着 valval 点嘤嘤嘤能量的绯狱丸，并且绯狱丸会吞噬该点的嘤嘤嘤能量，使得该点的嘤嘤嘤能量变为 val−ai val - a_i 点，aia_i 为出现绯狱丸的前一刻，该点所存在的嘤嘤嘤能量。
22 ll rr 表示绯玉丸会带着八重樱出现在[ ll , rr ]间的任意一点。八重樱为了尽快升级她的嘤嘤刀，会获取该区间上最大的嘤嘤嘤能量。特殊的，为了保卫八重村，当 ll , rr 之间存在绯狱丸时，八重樱会优先用她的嘤嘤刀对付绯狱丸，并获得绯狱丸此时拥有的 aia_i 点嘤嘤嘤能量。
33 ll rr valval 绯玉丸会嘤嘤嘤，使得[ ll , rr ]上的每一个地点的嘤嘤嘤能量增加 valval 点(包括绯狱丸)。

输入格式

第一行为 22 个数 nn , mm。
第二行为 nn 个数，分别表示八重街上每个地点的初始嘤嘤嘤能量。
接下来 mm 行，每行会发生 33 个事件中的一个，输入格式为题目描述中的格式。

输出格式

对于每一个事件 22 ，你应当输出八重樱在该事件中获取的嘤嘤嘤能量并换行。
当所有事件结束时，如果嘤嘤刀积累的能量小于 1000010000 ，你应当输出 QAQQAQ 。
如果在[ 1000010000 , 1000000010000000 )间，你应当输出 SakuraSakura。
如果都不符合，请输出 iceice。

样例 #1

样例输入 #1

CPP
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

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

样例 #2

样例输入 #2

CPP
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

CPP
10
QAQ

样例 #3

样例输入 #3

CPP
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

CPP
10000
8000
9000
Sakura

提示

对于所有的数据：
最终答案都会在 [0,231−1][0,2^{31}-1] 范围内；
nn , mm ⩽\leqslant 100000100000。
值得注意的是，无论八重樱是获取了某一地点的嘤嘤嘤能量还是击败了某一地点的绯狱丸，该地点的嘤嘤嘤值都应当清零而不是保留原来的数值。
对于事件 22 ，题目保证每个事件中最多出现 11 只绯狱丸。如果出现多个最大值，在每次比较时，请选择靠右的(std默认的)。
CPP
#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

*/

回复

共 5 条回复，欢迎继续交流。

正在加载回复...