专栏文章

已完成今日这实在是一个三岁小宝宝都会的简单题大学习

FForgotten_freopen
P14353题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@minfyusa
此快照首次捕获于
2025/12/02 01:47
3 个月前
此快照最后确认于
2025/12/02 01:47
3 个月前
查看原文
考场推这题结论推错了被额外硬控 1h 才切，印象深刻，遂写题解。
题目相当于要求你对 b′b' 数组的每一个前缀求一遍 g(b)g(b)，强制在线。
因为我们可能还不如三岁小宝宝，所以我们先来思考对于一个完整的数组 cc 如何求 g(c)g(c)。
众所周知，∣x−y∣\vert x - y\vert 的结果为 max⁡(x,y)−min⁡(x,y)\max(x,y) - \min(x,y)。假设 x<yx < y，那么在 ∣x−y∣\vert x - y\vert 中 yy 做正贡献，xx 做负贡献。
也就是说，在 g(c)g(c) 中，会有 n−1n - 1 个数做正贡献，n−1n - 1 个数做负贡献。这个应该不是三岁小宝宝也看得出来。
但是这个东西去搞的话并不好贪心或者 dp，因为会存在两个数只有一次贡献，而剩下 n−2n - 2 个数有两次贡献，显然我们不可能枚举哪两个数只做一次贡献，否则你会被三岁小宝宝肘飞（bushi）。
那怎么办？难道我们要被三岁小宝宝吊打了吗？
不可能。
我们的红色上档山药大神曾经说过这么一句话：
以“限制”换取升级，这个最为精妙的解密步骤恰巧与信竞解题中的“换个方向思考”完美契合。
这告诉我们，从多角度思考同一个问题，很可能会带来更大的收获。
你问在哪说的？这不重要。
说回正题。如果我们直接考虑哪些数做几次贡献，这很不好搞；但是如果我们先限制所有数的贡献次数一样，都是两次呢？
这个时候做法就很显然了，贪心让最大的那些数用掉正贡献，最小的那些数用掉负贡献即可。
nn 为偶数时，显然可以让最大的 n2\frac{n}{2} 个数用完正贡献，最小的 n2\frac{n}{2} 个数用完负贡献；而 nn 为奇数时，中位数的正贡献和负贡献都是一次，恰好抵消。这并不难。也就是说，此时的答案就是 cc 中最大的 ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor 个数之和减去 cc 中最小的 ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor 个数之和的 22 倍。
那么我们如何让所有数都做两次贡献呢？
——把数组的两头接起来，拼链成环即可。
当然，我们不可能就把这所有 2n2n 次贡献作为答案输出，还要减去一个正贡献和一个负贡献。
我们要让 g(c)g(c) 最大，那么我们肯定希望减去的 (正贡献−负贡献)(正贡献 - 负贡献)（设为 h(c)h(c)）最小。假设我们已经将 cc 中最大的 ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor 个数扔进了一个大根堆 SS，将 cc 中最小的 ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor 个数扔进了一个小根堆 TT，那么减去的 h(c)h(c) 就是在两个堆中各选出来的一个数之差（大减小）。显然，为了使减去的 h(c)h(c) 最小，我们直接取两个堆的堆顶即可（nn 为奇数时要特判一下，因为有一个元素不在 SS 或 TT 里）。
至此，我们完成了一道三岁小宝宝都会做的题（？）。
（贪心和构造能力比较强的大佬会发现其实可以直接从链的情况得出这个贪心的结论，我弯弯绕绕写了这么多，一个是为了给大家介绍限制换取升级的思想，另一方面也是为了展示我这个左右脑互搏的奶龙在考场上的真实思路。）
不过到这里其实原题的做法也差不多出来了。
具体地，对于每一个 ii（当前询问）：
如果 ii 为奇数，那么这个新元素 bi′b'_i 可能会成为 SS 或 TT 中的一员，所以我们把 bi′b'_i 分别和 SS 和 TT 的堆顶进行比较，如果符合条件就弹出堆顶并加入 bi′b'_i。
此时不管 bi′b'_i 有没有弹出一个堆顶（注意到同一个元素不可能把两个堆的堆顶都弹出），都会存在一个元素没有进堆，设它为 bj′b'_j。根据 SS 和 TT 维护的内容（这一点可以回顾上面的粗体部分），我们可以知道：bj′b'_j 就是那个恰好做一次正贡献和一次负贡献的元素。（这也是我们不把它加入 SS 或 TT 的原因——因为我们的 h(b′)h(b') 不可能是 bj′b'_j 的一正一负两次贡献。）此时我们的 h(c)h(c) 便可以在 SS 的堆顶与 bj′b'_j 的差和 TT 的堆顶与 bj′b'_j 的差中取最小值。
如果 ii 为偶数，那么我们上一轮用剩下的 bj′b'_j 和这一轮新来的 bi′b'_i 就可以考虑进堆了，将这两个数之间比较一下大小来决定谁进 SS 谁进 TT 即可。进完后，我们的 h(c)h(c) 就可以直接取 SS 的堆顶与 TT 的堆顶的差。
终于！我们可以吊打三岁小宝宝了！（光速逃
CPP
#include <bits/stdc++.h>
#define N 3000000
#define M 1
#define K 1
#define INF 1
#define mod 1
#define int1 long long
using namespace std;
int1 n,i,lastans,ans;
priority_queue<int1> small;//小的元素放的堆，即 S
priority_queue<int1,vector<int1>,greater<int1> > big;//大的元素放的堆，即 T
int1 bsum,ssum,minn,lll;
//中间的快读部分已省略
int main(){
	n = read();
	bool type = read();
	for(i = 1; i <= n; i++){
		const int1 now = read() ^ (type ? lastans : 0);
		if(i & 1){//奇数情况
			lll = now;
			if(i > 1){
				if(lll < small.top()){
					small.push(now);
					lll = small.top();
					small.pop();
					ssum -= (lll - now) << 1;
				}
				if(lll > big.top()){
					big.push(now);
					lll = big.top();
					big.pop();
					bsum += (now - lll) << 1;
				}
				minn = min(lll - small.top(),big.top() - lll);
			}
		}else{//偶数情况
			if(now < lll){
				small.push(now);
				ssum += now << 1;
				big.push(lll);
				bsum += lll << 1;
			}else{
				big.push(now);
				bsum += now << 1;
				small.push(lll);
				ssum += lll << 1;
			}
			minn = big.top() - small.top();
		}
		lastans = bsum - ssum - minn;
		ans ^= lastans;
	}
	pe(ans);
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...