题解：P4692 [Ynoi2016] 谁的梦
xiezheyuan
·
·
题解
简要题意
给定 n 个序列 a_1,\cdots,a_n，第 i 个序列长度为 l_i。
有 m 次询问，每次询问给出 x,y,z，表示 a_{x,y}\gets z。
在所有修改之前，以及每次修改之后，你需要输出：对于每一个序列选取一个子串，将所有子串拼接而成的序列的颜色数，称为这种选取方法的权值，你需要求出所有选取方法的权值之和。答案对 19260817 取模。
## 思路
毁人心智的大型拆贡献题，个人感觉其实分类讨论成分不大。
首先离线离散化，然后考虑每一种颜色对答案的贡献。发现拼接而成的序列必须有这种颜色比较困难，正难则反，改为考虑必须没有这种颜色。
我们很容易列出对于某种颜色 $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：
```cpp
#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
```