自动搬运

查看原文

来自洛谷，原作者为

	Anxiomgh NOIP 2023 RP++

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

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

以下是正文

---

本蒟蒻不会写 multiset，于是写了一发优先队列（逃）。 如有谬误，大家敬请指正。

Sol

首先考虑操作 Query。

设 $g(G_{1},G_{2},...G_{n})$ 表示将 $G_{1},G_{2},...G_{n}$ 以任意方式合并，易得引理 1：

合并方式 $g(G_{1},G_{2},...G_{i - 1},G_{i+1},...G_{n}) \to G_{i}$ 可以使 $G_{i}$ 中的合并后的最大值最小。

设 $w_{i}$ 为将所有组全部合并到组 $G_{i}$ 后的最大值的最小值，$v_{i}$ 为 $G_{i}$ 中原来的的最大值，$sum$ 为总糖果数，写成表达式为：

$$w_{i} = v_{i} + \frac{sum - f_{i}}{\sum_{j = 1}^n{S_{j}}} $$

可以发现，$O(n)$ 的预处理即可求得序列 $w$。那么原问题就转化成了求 $w$ 中的最小值和多次 Change 后 $w$ 中的最小值。

我们再来研究一下 Change 操作对序列 $w$ 的影响。

设共有四个组 $G_{1},G_{2},G_{3},G_{4}$，将 $G_{2}$ 修改为 $G_{3}$。

• 对于 $G_{1}$ 和 $G_{4}$，修改操作并不影响它们的最大值，因此 $w_{1}$ 和 $w_{4}$ 的值不改变。即：

  $w_{1}' = w_{1} = v_{1} + \frac{f_{2} + f_{3} + f_{4}}{S_{1} + S_{2}+ S_{3} + S_{4}},w_{4}' = w_{4} = v_{4} + \frac{f_{1} + f_{2} + f_{3}}{S_{1} + S_{2}+ S_{3} + S_{4}}$

• 对于 $G_{3}$，进行分类讨论：

  1. 如果 $v_{2} \leq v_{3}$，$w_{3}' = v_{3} + \frac{f_{1} + f_{4}}{S_{1} + S_{2}+ S_{3} + S_{4}}$，有 $w_{3}' < w_{3}$。

  2. 如果 $v_{2} > v_{3}$，$w_{3}' = v_{2} + \frac{f_{1} + f_{4}}{S_{1} + S_{2}+ S_{3} + S_{4}}$，有 $w_{3}' < w_{2}$。

综上所述，可得引理 2：当 $G_{i}$ 被修改成 $G_{j}$ 时，一定存在：

$$w_{j}' < w_{j}(v_{i} \leq v_{j})$$ $$w_{j}' < w_{i}(v_{i} > v_{j})$$

这样就可以用优先队列维护了。

不难发现，对于每一次 Change，都会对应着一个组被删除，一个 $v_{x}$ 消失，这个 $v_{x}$ 是参与比较的两个最大值中较小的一个。因为在此后任意 $G_{i}$ 中的最大值一定不为 $v_{x}$，$v_{x}$ 就一定不会参与 $w$ 的计算。建一个数组记录被淘汰的 $v_{x}$ 的下标 $x$，在优先队列中访问到下标被记录的元素直接 pop 掉即可。

而对于存留下来的另一个 $v_{y}$，它所对应的 Change 前的 $w$ 虽然在优先队列中也是不合法的，但将新生成的 $w'$ push 进优先队列，$w'$ 一定排在它前面，即 $w' < w$。所以它永远不会被访问到，这就保证了算法的正确性。

开一个 $fa$ 数组记录最大值的来源，并不断更新 $v$，就可以轻松处理 Change 的问题了。

具体实现请看代码 (QwQ)

代码

ll n, m, k, sum = 0;
ll a[MAXN], b[MAXN];
ll f[MAXN], v[MAXN], S[MAXN], w[MAXN], fa[MAXN];
bool flag[MAXN];
struct item
{
	ll pos, val; // pos 表示 G_{i} 中最大值的原下标 
	bool operator<(const item& x)const
	{
		return x.val < val;
	}
};
priority_queue<item>q;

void init() // 读入并初始化 
{
	n = read(), m = read(), k = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) b[i] = read();
	
	for (int i = 1; i <= n; i++)
		S[a[i]]++, f[a[i]] += b[i], v[a[i]] = max(v[a[i]], b[i]), sum += b[i];
		
	for (int i = 1; i <= n; i++) 
		w[i] = v[i] * n + sum - f[i]; // 计算 w（分子部分） 
		
	for (int i = 1; i <= k; i++) 
		q.push({i, w[i]}); // 将所有 w push 进队列里 
	for (int i = 1; i <= n; i++) fa[i] = i; // 初始化所有组中的最大值下标 
}

ll pow(ll x, ll temp)
{
	ll res = 1;
	for (; temp; temp >>= 1, x = x * x % p) 
		if (temp & 1) res = res * x % p;
	return res;
}
int main()
{
	init();
	while (m--)
	{
		string op;
		cin >> op;
		if (op == "Change")
		{
			int x, y;
			x = read(), y = read();
			f[y] += f[x];   //update
			S[y] += S[x];
			if (max(v[x], v[y]) == v[x])
				flag[fa[y]] = true, fa[y] = fa[x]; // 更新 G_{y} 中的最大值下标
			else
				flag[fa[x]] = true; // G_{x} 被删除，不用更新 fa_{x} 
			v[y] = max(v[x], v[y]); // 更新最大值 
			ll z = v[y] * n + sum - f[y]; // 计算 w'（分子部分） 
			q.push({fa[y], z}); // 将 G_{y} 中最大值的原下标和 w' push 进队列 
		}
		else if (op == "Query")
		{
			while (flag[q.top().pos] == true) // 如果队头元素中包含的最大值已被淘汰
			{
				q.pop(); 
			}
			ll ans = ((q.top().val % p) * pow(n, p - 2)) % p; // 有理数取余
			cout << (ans % p + p) % p << endl;
		}
	}
}