题解 P4692 【[Ynoi2016]谁的梦】

· · 题解

简单容斥+毒瘤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中可以规避掉很多细节。

代码：

#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);
    }
}