s2oj1651 【2022.10.15】灯 (light)
link。
首先通过经典的点减边容斥将极长连续段转化为求点亮的灯的个数减去相邻两个灯均点亮的对数。
点亮的灯的个数是简单的。接下来考虑如何计算相邻两个均被点亮的灯的对数。
考虑根号分治。
-
首先有一个显然的暴力是直接枚举所有颜色为 \(x\) 的点的两边，然后检查其是否被点亮。这个暴力能够处理相同颜色点数较少的情况。
-
对于点数较多的情况，这样的点一定不会很多。那么我们在更新周围小点的时候可以顺便维护一下如果翻转大点会造成怎样的贡献。
具体地，翻转一个颜色 \(x\) 时，若 \(x\) 的个数较少则暴力计算与其相邻的点是否被点亮，同时对其周围的大点打上贡献的标记。若 \(x\) 的个数较多则答案即为标记，然后更新其周围的大点的贡献即可。
时间复杂度 \(\mathcal{O}(n \sqrt n)\)。
code
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 200005
#define M 505
int n,q,m,w[N],len,ans1,ans2,vis[N];
vector<int> g[N],ins;
int val[M][M],tag[M],id[N],num,dis[N];
int main(){
read(n,q,m),len=sqrt(n)+1;
for(int i=1;i<=n;i++) read(w[i]),g[w[i]].emplace_back(i);
for(int i=1;i<=m;i++)
if(g[i].size()>len) ins.emplace_back(i),id[i]=++num;
for(int i=1;i<=n;i++){
if(id[w[i]]&&id[w[i+1]]&&w[i]!=w[i+1]) val[id[w[i]]][id[w[i+1]]]++;
if(id[w[i]]&&id[w[i-1]]&&w[i]!=w[i-1]) val[id[w[i]]][id[w[i-1]]]++;
if(w[i]==w[i-1]) dis[w[i]]++;
}
for(int qq=1,x;qq<=q;qq++){
read(x),vis[x]^=1;
int t=vis[x]?1:-1;
ans1+=t*g[x].size(),ans2+=t*dis[x];
if(g[x].size()<=len){
for(auto v:g[x]){
if(vis[w[v+1]]&&x!=w[v+1]) ans2+=t;
if(vis[w[v-1]]&&x!=w[v-1]) ans2+=t;
if(id[w[v+1]]&&x!=w[v+1]) tag[id[w[v+1]]]+=vis[w[v+1]]!=vis[x]?1:-1;
if(id[w[v-1]]&&x!=w[v-1]) tag[id[w[v-1]]]+=vis[w[v-1]]!=vis[x]?1:-1;
}
}else{
ans2+=tag[id[x]],tag[id[x]]=-tag[id[x]];
for(auto v:ins)
if(x!=v&&vis[v]) ans2+=t*val[id[v]][id[x]];
}
put('\n',ans1-ans2);
}
return 0;
}