[Medium] P4692 [Ynoi Easy Round 2016] 谁的梦

xiezheyuan2025/1/21约 1454 字大约 7 分钟

简要题意

给定 $n$ 个序列 $a_1,\cdots,a_n$ ，第 $i$ 个序列长度为 $l_i$ 。

有 $m$ 次询问，每次询问给出 $x,y,z$ ，表示 $a_{x,y}\gets z$ 。

在所有修改之前，以及每次修改之后，你需要输出：对于每一个序列选取一个子串，将所有子串拼接而成的序列的颜色数，称为这种选取方法的权值，你需要求出所有选取方法的权值之和。答案对 $19260817$ 取模。

$1\leq n,m,l_i\leq 10^5,1\leq \sum l_i\leq 10^5$ 。

思路

毁人心智的大型拆贡献题，个人感觉其实分类讨论成分不大。

首先离线离散化，然后考虑每一种颜色对答案的贡献。发现拼接而成的序列必须有这种颜色比较困难，正难则反，改为考虑必须没有这种颜色。

我们很容易列出对于某种颜色 $k$ ，拼接而成的序列必须没有这种颜色的方案数为 $\prod_i w(i,k)$ ，其中 $w(i,k)$ 表示从 $a_i$ 中选取一个子串，使得不出现 $k$ 的方案数。

然后考虑如何求出 $w(i,k)$ ，可以将 $a_i$ 中所有等于 $k$ 的元素取出来，这可以看成将序列分成了 $k+1$ 段，每一段（不包含断点）的子串数量之和就是答案。为了减少分类讨论，我们钦定 $0,l_i$ 总是断点，并且用 set 记录断点情况。

为了方便后面的修改，我们对于每一个序列 $a_i$ ，离线后处理出哪些颜色与它有关，也就是在某个时刻，序列 $a_i$ 中出现过这个颜色。然后对于所有与 $a_i$ 相关的颜色，将一个 set 关联到 $a_i$ ，表示对应颜色的断点情况（当然，为了方便快速找到这个 set，你可能需要用一个 map），由于这样的 set 最多只有 $O(m+\sum l_i)$ 个，所以开的下。

接着考虑如何处理修改，我们可以看成这个元素的贡献消失，然后加入新的点的贡献，这一部分非常简单，但是要注意细节，具体看代码。

你可能发现了，为了维护贡献的消失和新增，我们需要维护一个颜色的答案，而如果出现了一个序列全是某一种颜色，那么答案会为 $0$ ，这样后面的处理会出现问题。一种比较好的解决方法是维护每种颜色对应的贡献为 $0$ 的序列数量，具体可以参考代码中 node 的实现。

时间复杂度 $O(n\log n)$ ，默认 $n,m,\sum l_i$ 同阶。

代码

自认为写的挺清晰的，但是仍然有 3.8 KB：

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

constexpr int mod = 19260817, inv2 = (mod + 1) >> 1;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

struct node{
    int val, cnt;
    node() : val(1), cnt(0) {}
    void muls(int x){ !x ? ++cnt : val = Mul(val, x); }
    void divs(int x){ !x ? --cnt : val = Mul(val, fastpow(x, mod - 2)); }
    int operator()(){ return cnt ? 0 : val; }
};

const int N = 1e5 + 5;
int n, m, len[N], buf[N << 1];
node ans[N << 1];
vector<int> a[N];

struct opt{
    int a, b, x;
} opts[N];

vector<set<int>> col[N];
map<int,int> colp[N];
vector<int> f[N];

void create(int i, int x){
    colp[i][x] = col[i].size();
    col[i].push_back(set<int>());
    col[i].back().insert(0);
    col[i].back().insert(len[i] + 1);
}

int subs(int x){ return Mul(inv2, Mul(x, Add(x, 1))); }
int subs(int l, int r){ return subs(r - l + 1); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m; int tot = 0;
    for(int i=1;i<=n;i++) cin >> len[i], a[i].resize(len[i] + 1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=len[i];j++) cin >> a[i][j], buf[++tot] = a[i][j];
    }
    for(int i=1;i<=m;i++) cin >> opts[i].a >> opts[i].b >> opts[i].x, buf[++tot] = opts[i].x;
    sort(buf + 1, buf + tot + 1);
    tot = unique(buf + 1, buf + tot + 1) - buf - 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=len[i];j++) a[i][j] = lower_bound(buf + 1, buf + tot + 1, a[i][j]) - buf;
    }
    for(int i=1;i<=m;i++) opts[i].x = lower_bound(buf + 1, buf + tot + 1, opts[i].x) - buf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=len[i];j++){
            int x = a[i][j];
            if(!colp[i].count(x)) create(i, x);
            col[i][colp[i][x]].insert(j);
        }
    }
    for(int i=1;i<=m;i++){
        int a = opts[i].a, x = opts[i].x;
        if(!colp[a].count(x)) create(a, x);
    }
    int total = 1;
    for(int i=1;i<=n;i++) total = Mul(total, subs(len[i]));
    for(int i=1;i<=tot;i++) ans[i].muls(total);
    for(int i=1;i<=n;i++){
        f[i].resize(col[i].size());
        for(auto [c, j] : colp[i]){
            int tmp = 0;
            for(auto it1=col[i][j].begin(),it2=next(it1);it2!=col[i][j].end();it1++,it2++){
                int l = *it1, r = *it2;
                tmp = Add(tmp, subs(l + 1, r - 1));
            }
            f[i][j] = tmp;
            ans[c].divs(subs(len[i])), ans[c].muls(tmp);
        }
    }
    total = Mul(total, tot);
    for(int i=1;i<=tot;i++) total = Sub(total, ans[i]());
    cout << total << '\n';
    for(int i=1;i<=m;i++){
        int x = opts[i].a, y = opts[i].b, z = opts[i].x;
        int ori = a[x][y], pos = colp[x][ori];
        auto it = col[x][pos].find(y);
        auto pre = prev(it), nxt = next(it);
        total = Add(total, ans[ori]());
        ans[ori].divs(f[x][pos]);
        f[x][pos] = Sub(f[x][pos], subs(*pre + 1, *it - 1));
        f[x][pos] = Sub(f[x][pos], subs(*it + 1, *nxt - 1));
        f[x][pos] = Add(f[x][pos], subs(*pre + 1, *nxt - 1));
        ans[ori].muls(f[x][pos]);
        total = Sub(total, ans[ori]());
        col[x][pos].erase(it);
        pos = colp[x][z];
        total = Add(total, ans[z]());
        ans[z].divs(f[x][pos]);
        nxt = col[x][pos].upper_bound(y), pre = prev(nxt);
        f[x][pos] = Add(f[x][pos], subs(*pre + 1, y - 1));
        f[x][pos] = Add(f[x][pos], subs(y + 1, *nxt - 1));
        f[x][pos] = Sub(f[x][pos], subs(*pre + 1, *nxt - 1));
        ans[z].muls(f[x][pos]);
        total = Sub(total, ans[z]());
        col[x][pos].insert(y);
        a[x][y] = z;
        cout << total << '\n';
    }
    return 0;
}

// Written by xiezheyuan