题解 P4692 【[Ynoi2016]谁的梦】
诗乃
2019-11-07 08:31:12
简单容斥+毒瘤STL。
设长度为$n$的序列共有$G(n)$个子区间，则：
$$G(n)=\frac{n(n+1)}{2}$$
考虑分开计算每个颜色的贡献，利用补集转化的思想，设颜色$c$的总贡献为$res_c$，则：
$$res_c=\prod_{i=1}^{n}G(len_i)-\prod_{i=1}^{n}ans_{c,i}$$
其中$ans_{c,i}$为第$i$个序列中**不包含**颜色$c$的子区间个数。
考虑如何求出$ans_{c,i}$。不难发现，使一个子区间不包含某种颜色，则这个区间的左右端点一定在相邻两个颜色$c$之间。可以看成一个颜色将某个序列分成$m$个长度分别为$l_i$的子序列，则可以得出：
$$ans_{c,i}=\sum_{i=1}^{m}G(l_i)$$
对于每个颜色在每个序列内的出现位置维护$set$即可求出$ans_{c,i}$。
考虑如何统计总答案，设总答案为$ANS$，颜色数量为$cntcol$则：
$$ANS=\sum_{i=1}^{cntcol}res_c=\sum_{i=1}^{cntcol}\prod_{i=1}^{n}G(len_i)-\sum_{i=1}^{cntcol}\prod_{i=1}^{n}ans_{c,i}$$
维护$all_c=\prod_{i=1}^{n}ans_{c,i}$，$S=\sum_{i=1}^{cntcol}all_c$即可求出答案。
考虑如何进行修改。将某个位置的颜色修改可以看成在某颜色的$set$中删除一个位置后在另一个颜色的$set$中添加一个位置。
考虑添加/删除一个位置产生的影响。实质上是将一段划分出的子序列分成两段或将两段合成一段，直接维护统计答案即可。
细节：维护过程中可能存在$all_c$变成$0$又变回不为$0$的情况，容易出错，需要特别维护。将位置$-1$和$len_i$插入所有颜色的$set$中可以规避掉很多细节。
代码：
```cpp
#include <bits/stdc++.h>
#define sIT set<int>::iterator
using namespace std;
const int MAXN = 200050, P = 19260817, inv2 = 9630409;
int read() {
char ch; int x; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; return x;
}
int inv(int a) {
if(a == 0) return 1;
int b = P-2, res = 1;
for(; b; a = 1ll*a*a%P, b >>= 1) if(b&1) res = 1ll*res*a%P;
return res;
}
int G(int _n) {return 1ll*_n*(_n+1)%P*inv2%P;}
struct Z {
int p, c;
bool operator < (const Z &b) const {
return p == b.p ? c < b.c : p < b.p;
}
};
map <Z, int> id; map <int, int> idc;
int n, m, len[MAXN], sigma, _ans[MAXN], all[MAXN], S, piL, cnt, cntcol, _0[MAXN], _all[MAXN];
bool __0[MAXN];
vector <int> a[MAXN]; set <int> s[MAXN];
void modify(int p, int _n, int c, int tp) {
bool tmp = __0[p];
S = (S + P - all[c]) % P;
if(!tmp) _all[c] = 1ll*_all[c]*inv(_ans[p])%P;
if(!tmp) all[c] = 1ll*all[c]*inv(_ans[p])%P;
if(!tp) _ans[p] = (_ans[p] - G(_n) + P) % P;
else _ans[p] = _ans[p] + G(_n) % P;
if(_ans[p]) _all[c] = 1ll*_all[c]*_ans[p]%P;
if(!_ans[p] && !tmp) __0[p] = 1, ++_0[c];
if(_ans[p] && tmp) __0[p] = 0, --_0[c];
all[c] = 1ll*all[c]*_ans[p]%P;
if(!_0[c]) all[c] = _all[c];
S = (S + all[c]) % P;
}
void del(int p, int t) {
int c = a[p][t], u = id[(Z){p, c}];
sIT it = s[u].lower_bound(t), itl, itr;
itl = (--it)++; itr = (++it)--;
modify(u, (*itr)-(*itl)-1, c, 1);
modify(u, (*it)-(*itl)-1, c, 0);
modify(u, (*itr)-(*it)-1, c, 0);
s[u].erase(it);
}
void add(int p, int t) {
int c = a[p][t], u = id[(Z){p, c}];
sIT itr = s[u].upper_bound(t), itl;
itl = (--itr)++;
modify(u, t-(*itl)-1, c, 1);
modify(u, (*itr)-t-1, c, 1);
modify(u, (*itr)-(*itl)-1, c, 0);
s[u].insert(t);
}
void getans() {
for(int i = 1; i <= n; ++i)
for(int j = 0; j < len[i]; ++j)
add(i, j);
}
void update(int x, int y, int k) {del(x, y); a[x][y] = k; add(x, y);}
int main() {
n = read(); m = read(); piL = 1;
for(int i = 1; i <= n; ++i) len[i] = read(), piL = 1ll*piL*G(len[i])%P;
for(int i = 1; i <= n; ++i)
for(int x, j = 0; j < len[i]; ++j) {
x = read();
if(!idc[x]) {
sigma = (sigma + piL) % P;
idc[x] = ++cntcol;
_all[cntcol] = all[cntcol] = piL; S = (S + all[cntcol]) % P;
} x = idc[x];
Z t; t = (Z) {i, x};
if(!id[t]) {
id[t] = ++cnt;
s[cnt].insert(-1); s[cnt].insert(len[i]);
_ans[cnt] = G(len[i]);
}
a[i].push_back(x);
}
getans();
printf("%d\n", (sigma+P-S)%P);
for(int x, y, k; m--; ){
x = read(); y = read(); k = read();
if(!idc[k]) {
sigma = (sigma + piL) % P;
idc[k] = ++cntcol;
_all[cntcol] = all[cntcol] = piL; S = (S + all[cntcol]);
} k = idc[k];
Z t; t = (Z) {x, k};
if(!id[t]) {
id[t] = ++cnt;
s[cnt].insert(-1); s[cnt].insert(len[x]);
_ans[cnt] = G(len[x]);
}
update(x, y-1, k);
printf("%d\n", (sigma+P-S)%P);
}
}
```