自动搬运

查看原文

来自洛谷，原作者为

	WanderFreeFish Continue for love,give up for reality.

搬运于2025-08-24 23:16:31，当前版本为作者最后更新于2025-07-29 16:49:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

这题有一个很重要的一点，就是最多分成两个序列。如果存在分成多个序列的解，那么一定可以合并变成两个。

对于多个中位数相同的序列 $a$，令这个中位数位置为 $pos$，每个序列排序之后，$pos$ 右边的数都大于等于 $a_{pos}$，左边的数都小于等于 $a_{pos}$，且这两个值一定相等。序列合并排序后这两个值分别求和，两边仍然相等，故中位数相等（拙劣的证明）。

于是题目变成了，把一个序列分成两个，使其中位数相等。考虑枚举分割线，判断左右两边的中位数是否相等。

Specifically

中位数可以预处理，因为我们只需要前缀与后缀数组的中位数。从前往后遍历，先把当前位置的数加进去，然后求第 $k$ 小。那做法可太多了。由于我太菜了不会可持久化线段树，还是用平衡树吧。后缀的预处理同理。

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
#define lson tr[root].ls
#define rson tr[root].rs

const int MAXN = 2e5 + 10;

struct node {
	int ls, rs, sz, val, key;
	node () {
		ls = rs = sz = val = key = 0;
	}
};

struct fanhaoqiang {
public:
	std::vector <node> tr; int allroot, tot;
	
	fanhaoqiang () {
		allroot = tot = 0;
		tr.resize(1);
	}
	
private:
	int newnode (int val) {
		tr.push_back(node());
		tr[++tot].val = val;
		tr[tot].sz = 1;
		tr[tot].key = rand();
		return tot;
	}
	
	void split (int root, int &l, int &r, int val) {
		if (root == 0) {
			l = r = 0;
			return;
		}
		else if (tr[root].val <= val) {
			l = root;
			split(rson, rson, r, val);
		}
		else {
			r = root;
			split(lson, l, lson, val);
		}
		push_up(root);
	}
	
	void push_up (int root) {
		tr[root].sz = tr[lson].sz + tr[rson].sz + 1;
	}
	
	int merge (int l, int r) {
		if (!l || !r)
			return (l | r);
		else if (tr[l].key <= tr[r].key) {
			tr[l].rs = merge(tr[l].rs, r);
			push_up(l);
			return l;
		}
		else {
			tr[r].ls = merge(l, tr[r].ls);
			push_up(r);
			return r;
		}
	}
	
public:
	int rank_kth (int root, int k) {
		if (tr[root].sz < k) return -1;
		else if (tr[lson].sz + 1 == k) return tr[root].val;
		else if (tr[lson].sz >= k) return rank_kth(lson, k);
		else return rank_kth(rson, k - tr[lson].sz - 1);
	}
	
	void insert (int val) {
		int x, y;
		split(allroot, x, y, val - 1);
		allroot = merge(merge(x, newnode(val)), y);
	}
}twd, bwd; // toward,backward

int n, a[MAXN], pre[MAXN], suf[MAXN], flag;

int main () {
	std::cin >> n;
	
	for (int i = 1; i <= n; i++)
		std::cin >> a[i];
	
	pre[1] = a[1];
	twd.insert(a[1]);
	for (int i = 3; i <= n; i += 2) { //因为只能分成奇数长度，所以每次加 2
		twd.insert(a[i - 1]);
		twd.insert(a[i]);
		pre[i] = twd.rank_kth(twd.allroot, i / 2 + 1);
	}
	
	suf[n] = a[n];
	bwd.insert(a[n]);
	for (int i = n - 2; i >= 1; i -= 2) {
		bwd.insert(a[i]);
		bwd.insert(a[i + 1]);
		suf[i] = bwd.rank_kth(bwd.allroot, (n - i + 1) / 2 + 1);
	}
	
	
	for (int i = 1; i <= n; i += 2)
		if (pre[i] == suf[i + 1])
			flag = 1;
	
	if (flag) std::cout << "Yes";
	else std::cout << "No";
	
	return 0;
}

Other

但是这道题不管是主席树还是平衡树，都是蓝题，为什么这是一道绿题？

还有，这道题还可以跑得更快些。把范浩强换成红黑树就行。

由于篇幅以及洛谷剪贴板炸了，暂且放在这里。