[HEFFFF赛]Turn All The Lights On

题目

题目描述
有一排 $n$ 个灯，每个灯有一个 $1$ 到 $m$ 的颜色。一开始所有灯都是关着的。有 $q$ 次操作，每次改变某种颜色的灯的状态（即，对于所有颜色为 $v$ 的灯，若原来是开着的，就都关掉；若原来是关着的，就都打开），每次操作后你需要求出有多少个极长的开着的灯（无论颜色）的连续段。

数据范围与提示
$m\le n\le 10^5$ 并且 $q\le 10^5$ 。

思路

考虑在一个极长段的末尾计数。即，若一个灯是亮着的，而它右边的灯是关着的，那就提供 $1$ 的贡献。

然后转化成图论，建立两个虚点，分别表示 $\mathrm{o}\mathrm{n}/\mathrm{o}\mathrm{f}\mathrm{f}$，问题转化为，每次修改一个点，求导出子图的边数。

做过这个题的，应该会联想到很常见的大小点 $\mathtt{t}\mathtt{r}\mathtt{i}\mathtt{c}\mathtt{k}$ 。然后就 $\mathcal{O}(n\sqrt{n})$ 做完了。

代码

也可以用亮着的灯总数 $-$ 相邻两个都亮着的灯对数。

重要的问题：不能保留重边。因为大点的个数 $\le \sqrt{n}$ 必须推出边数 $\le \sqrt{n}$ 才能保证时间复杂度。我还以为是 $zxy$ 附体带来大常数呢。$\mathsf{H}\mathsf{a}\mathsf{n}\mathsf{d}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{e}\mathsf{v}\mathsf{i}\mathsf{l}$ 太强啦！

#include <cstdio> 
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MaxN = 100005;
typedef unordered_map<int,int>::iterator ddq;

unordered_map<int,int> g[MaxN];
int deg[MaxN]; // got in main()
void addEdge(int a,int b){
	++ g[a][b], ++ g[b][a];
}

int cnt[MaxN], val[MaxN], ans;
char tag[MaxN]; // if it's on
const int SqrtN = 330;
void modify(int x){
	for(ddq it=g[x].begin(); it!=g[x].end(); ++it){
		if(deg[x] < SqrtN) // it's a small node
			ans -= (1-2*tag[x])*tag[it->first]*it->second;
		val[it->first] += (1-2*tag[x])*it->second;
	}
	if(deg[x] >= SqrtN) // big node
		ans -= (1-2*tag[x])*val[x];
	ans += (1-2*tag[x])*cnt[x];
	tag[x] ^= 1; // opposite
}

int main(){
	int n = readint(); readint();
	int q = readint();
	int lst = readint(); ++ cnt[lst];
	for(int i=2,a; i<=n; ++i){
		if(lst == (a=readint())) continue;
		++ cnt[a], addEdge(lst,a), lst = a;
	}
	for(int i=1; i<=n; ++i)
		deg[i] = g[i].size();
	for(int i=1; i<=n; ++i){
		if(deg[i] < SqrtN) continue;
		ddq it = g[i].begin();
		while(it != g[i].end())
			if(deg[it->first] < SqrtN)
				g[i].erase(it ++);
			else ++ it; // go on
	}
	for(; q; --q,writeint(ans),putchar('\n'))
		modify(readint());
	return 0;
}