自动搬运

查看原文

来自洛谷，原作者为

	诗乃 あなた以上の人なんて、どこにもいないよ♡

搬运于2025-08-24 22:02:40，当前版本为作者最后更新于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$中可以规避掉很多细节。

代码：

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