A1570 优美的序列

// A1570 优美的序列 —— 计数 + 单点修改
//
// 优美的序列：存在 i，使得前 i 个数严格递减、后面的数严格递增（V 型，谷底是最小值）。
//
// 结论：设各个值的出现次数为 cnt[v]，最小值为 mn。
//   1) 谷底就是最小值，且最小值只能出现一次，故 cnt[mn] 必须为 1，否则答案为 0；
//   2) 其它每个值最多出现两次（左边一个、右边一个）：
//        出现 1 次：可以放左边或右边，2 种选择；
//        出现 2 次：必须左右各一个，1 种选择；
//        出现 >= 3 次：无解，答案为 0。
//   于是答案 = 2^(cnt 为 1 的值的个数 - 1) mod p。
//
// 修改用计数数组维护：cnt 为 1 的值的个数 s1、cnt >= 3 的值的个数 s3，
// 最小值用一个有序集合（存所有出现过的值）维护。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    ll p;
    cin >> n >> m >> p;

    vector<int> a(n + 1), cnt(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }

    int s1 = 0;  // 出现次数恰为 1 的值的个数
    int s3 = 0;  // 出现次数 >= 3 的值的个数
    set<int> present; // 当前出现过的值（用来取最小值）
    for (int v = 1; v <= n; v++) {
        if (cnt[v] == 1) s1++;
        if (cnt[v] >= 3) s3++;
        if (cnt[v] > 0) present.insert(v);
    }

    auto modpow = [&](ll base, ll e) {
        ll r = 1 % p;
        base %= p;
        while (e > 0) {
            if (e & 1) r = r * base % p;
            base = base * base % p;
            e >>= 1;
        }
        return r;
    };

    // cnt[v] 增加 delta 时同步维护 s1、s3 和 present
    auto change = [&](int v, int delta) {
        int before = cnt[v];
        if (before == 1) s1--;
        if (before >= 3) s3--;
        if (before == 0 && delta > 0) present.insert(v);
        cnt[v] += delta;
        int after = cnt[v];
        if (after == 1) s1++;
        if (after >= 3) s3++;
        if (after == 0) present.erase(v);
    };

    auto answer = [&]() -> ll {
        if (s3 > 0) return 0;              // 有某个值出现 >= 3 次，无解
        int mn = *present.begin();          // 当前最小值
        if (cnt[mn] != 1) return 0;         // 最小值必须只出现一次
        return modpow(2, s1 - 1);           // 其余「只出现一次」的值各有 2 种选择
    };

    cout << answer() << '\n';
    for (int i = 0; i < m; i++) {
        int x, k;
        cin >> x >> k;
        change(a[x], -1);
        change(k, 1);
        a[x] = k;
        cout << answer() << '\n';
    }
    return 0;
}