洛谷 4692 「Ynoi 2016」谁的梦

这个题感觉像蓝题吧（

首先考虑对每个颜色计算包含这种颜色的方案数，这可以用一个容斥解决。
即考虑用 n∏i=1(leni+12) 减去不包含这种颜色的方案数。
也就是考虑计算每个序列有多少个子串不包含这种颜色。
这个可以通过用 set 维护其出现位置处理。

然后还有若干细节（

代码：

#include <set>
#include <map>
#include <cstdio>
using namespace std;
const int N = 1e5;
const int C = 2e5;
const int mod = 19260817;
const int hash_mod = 70921;
int n,m;
int len[N + 5],A[N + 5],*a[N + 5];
int tot;
struct Hash
{
    int key[C + 5],val[C + 5],pre[C + 5],first[hash_mod + 5],tot;
    int find(int x)
    {
        int h = x % hash_mod;
        for(register int i = first[h];i;i = pre[i])
            if(key[i] == x)
                return i;
        return 0;
    }
    bool count(int x)
    {
        return find(x);
    }
    int &operator[](int x)
    {
        int h = x % hash_mod,it = find(x);
        if(!it)
            key[++tot] = x,pre[tot] = first[h],first[h] = it = tot;
        return val[it];
    }
} id;
struct Hash2
{
    int key[C + 5][2],val[C + 5],pre[C + 5],first[hash_mod + 5],tot;
    int find(int x,int k)
    {
        int h = ((long long)x * N + k) % hash_mod;
        for(register int i = first[h];i;i = pre[i])
            if(key[i][0] == x && key[i][1] == k)
                return i;
        return 0;
    }
    int &operator()(int x,int k)
    {
        int h = ((long long)x * N + k) % hash_mod,it = find(x,k);
        if(!it)
            key[++tot][0] = x,key[tot][1] = k,pre[tot] = first[h],first[h] = it = tot;
        return val[it];
    }
} val,vis;
struct note
{
    int x,y;
    inline note(int a = 0,int b = 0)
    {
        x = a,y = b;
    }
    inline bool operator<(const note &o) const
    {
        return x ^ o.x ? x < o.x : y < o.y;
    }
};
set<note> s[C + 5];
int inv[mod + 5];
struct Value
{
    int v,cnt;
    inline Value(int x = 0)
    {
        x ? (v = x,cnt = 0) : (v = cnt = 1);
    }
    inline Value(int x,int y)
    {
        v = x,cnt = y;
    }
    inline Value operator*(const Value &o) const
    {
        return Value((long long)v * o.v % mod,cnt + o.cnt);
    }
    inline Value operator/(const Value &o) const
    {
        return Value((long long)v * inv[o.v] % mod,cnt - o.cnt);
    }
    inline int val()
    {
        return cnt ? 0 : v;
    }
} sum[C + 5],init(1);
int ans;
inline int getid(int k)
{
    return id.count(k) ? id[k] : (sum[++tot] = init,id[k] = tot);
}
void insert(int x,int y,int k)
{
    k = getid(k);
    if(!vis(x,k)++)
        s[k].insert(note(x,0)),s[k].insert(note(x,len[x] + 1)),val(x,k) = (long long)len[x] * (len[x] + 1) / 2 % mod;
    set<note>::iterator it = s[k].insert(note(x,y)).first;
    int l = (--it)->y;
    ++it;
    int r = (++it)->y;
    int &v = val(x,k);
    ans = (ans + sum[k].val()) % mod,
    sum[k] = sum[k] / v,
    v = (v - (long long)(r - l - 1) * (r - l) / 2 % mod + mod) % mod,
    v = (v + (long long)(y - l - 1) * (y - l) / 2 % mod) % mod,
    v = (v + (long long)(r - y - 1) * (r - y) / 2 % mod) % mod,
    sum[k] = sum[k] * v,
    ans = (ans - sum[k].val() + mod) % mod;
}
void erase(int x,int y,int k)
{
    k = getid(k);
    set<note>::iterator it = s[k].find(note(x,y));
    int l = (--it)->y;
    ++it;
    int r = (++it)->y;
    int &v = val(x,k);
    ans = (ans + sum[k].val()) % mod,
    sum[k] = sum[k] / v,
    v = (v - (long long)(y - l - 1) * (y - l) / 2 % mod + mod) % mod,
    v = (v - (long long)(r - y - 1) * (r - y) / 2 % mod + mod) % mod,
    v = (v + (long long)(r - l - 1) * (r - l) / 2 % mod) % mod,
    sum[k] = sum[k] * v,
    ans = (ans - sum[k].val() + mod) % mod;
    s[k].erase(--it);
    if(!--vis(x,k))
        s[k].erase(note(x,0)),s[k].erase(note(x,len[x] + 1));
}
int main()
{
    scanf("%d%d",&n,&m),a[0] = A,inv[1] = 1;
    for(register int i = 2;i < mod;++i)
        inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
    for(register int i = 1;i <= n;++i)
        scanf("%d",&len[i]),a[i] = a[i - 1] + len[i - 1],init = init * ((long long)len[i] * (len[i] + 1) / 2 % mod);
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= len[i];++j)
            scanf("%d",a[i] + j),insert(i,j,a[i][j]);
    printf("%d\n",ans);
    for(int x,y,k;m;--m)
        scanf("%d%d%d",&x,&y,&k),erase(x,y,a[x][y]),insert(x,y,a[x][y] = k),printf("%d\n",ans);
}