这个题感觉像蓝题吧（
首先考虑对每个颜色计算包含这种颜色的方案数，这可以用一个容斥解决。
即考虑用 \(\prod\limits_{i=1}^n \binom{ {\rm len}_i + 1 }2\) 减去不包含这种颜色的方案数。
也就是考虑计算每个序列有多少个子串不包含这种颜色。
这个可以通过用 set 维护其出现位置处理。
然后还有若干细节（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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);
}