自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:43:30，当前版本为作者最后更新于2022-12-06 15:58:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，我们把“优美”的条件转化为：

• 存在一个波谷，使得从中间向两边分别严格单调递增。

显然波谷即当前 $a$ 中的最小值只能存在恰好一个，也就是说：当最小值不止一个时答案为 $0$。

那对于剩下的数呢？我们不难发现：

• 若存在一个出现次数 $> 2$ 的数，答案为 $0$。

显然你只能把这个数放在波谷两边，且一边至多一个——毕竟我们要求的时严格单调递增，而这个出现次数 $> 2$ 的数就没法放了。

那对于其他情况呢？我们可以通过如下方式构造一种合法的“优美”序列：

• 我们先处理那些恰好出现一次且非最小值的数，将其随意划分成两堆，把最小值放在中间，再把这两堆排序后分列两侧；然后我们再来处理那些恰好出现两次的数，根据大小在左右各插入一个（不难发现固定恰好出现一次的数的排列顺序后方案唯一）即可。

能按这种方式构造显然是一个充要条件。

由此，我们也可以得出答案：

• 令 $cnt$ 表示恰好出现一次且非最小值的数的个数，则答案为 $2^{cnt}$。

为什么呢？注意到我们在上面的构造中是把这 $cnt$ 个数随意划分成两堆的，且因为要排序，所以我们不关心顺序。于是方案数即为子集数量 $2^{cnt}$。

实现时，先预处理 $2$ 的幂，然后用一个桶维护每个数当前的出现次数，实现 add/del 操作维护恰好出现一次的数和出现次数 $> 2$ 的数的数量，再用一个 multiset 维护所有数（因为你需要动态维护最小值）即可。时间复杂度为 $O((n + m) \log n)$。

代码：

#include <set>
#include <cstdio>

using namespace std;

int cnt1 = 0, cnt2 = 0;
int power[500007], a[500007], cnt[500007];
multiset<int> s;

inline void init(int n, int p){
	power[0] = 1;
	for (register int i = 1; i <= n; i++){
		power[i] = power[i - 1] * 2 % p;
	}
}

inline int read(){
	int ans = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans;
}

inline void add(int x){
	cnt[x]++;
	s.insert(x);
	if (cnt[x] == 1){
		cnt1++;
	} else if (cnt[x] == 2){
		cnt1--;
	} else if (cnt[x] == 3){
		cnt2++;
	}
}

inline void output(){
	if (cnt2 > 0 || cnt[*s.begin()] > 1){
		printf("0\n");
	} else {
		printf("%d\n", power[cnt1 - 1]);
	}
}

inline void del(int x){
	cnt[x]--;
	s.erase(s.lower_bound(x));
	if (cnt[x] == 0){
		cnt1--;
	} else if (cnt[x] == 1){
		cnt1++;
	} else if (cnt[x] == 2){
		cnt2--;
	}
}

int main(){
	int n = read(), m = read(), p = read();
	init(n - 1, p);
	for (register int i = 1; i <= n; i++){
		a[i] = read();
		add(a[i]);
	}
	output();
	for (register int i = 1; i <= m; i++){
		int x = read(), k = read();
		del(a[x]);
		a[x] = k;
		add(k);
		output();
	}
	return 0;
}