题解 「DPOI-1」优美的序列

Leasier · 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;
}