P8379 [PFOI Round1] Two Operations 题解

Anxiomgh · 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 为总糖果数，写成表达式为：

可以发现，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} 时，一定存在：

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

不难发现，对于每一次 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;
        }
    }
}