前言
唯一的一盏明灯也无精打采了,与身旁的分块互相搀扶着,我只觉得前路一片黑暗。
题目
题目描述
夜深人静之时,爱玩的妹妹 \(\tt ZXY\) 会冒出来玩路灯。这一排路灯共有 \(n\) 个,每个路灯都有一种颜色(这正是她觉得有意思的地方),共 \(m\) 种颜色。
她要做的就是反复开关一种颜色的灯,但她觉得一个人玩太没意思了,所以她会问你这些开着的灯的极长连续段有多少个。
输入格式
第一行三个整数 \(n,m,q\),分别表示路灯个数,颜色总数,操作次数。
第二行 \(n\) 个整数 \(c_i\) 表示路灯的颜色。
接下来 \(q\) 行,每行一个整数,表示对哪一种颜色的路灯进行操作。
输出格式
\(q\) 行,每行一个答案。
样例
样例输入1
3 2 5
1 2 1
1
2
1
2
2
样例输出1
2
1
1
0
1
数据规模
\(\tt Subtask 1 (13pts)\) \(:n,q\le 5000\)。
\(\tt Subtask 2 (35pts)\) \(:m<=100\)。
\(\tt Subtask 3 (52pts)\) \(:\)无特殊限制。
对于全部数据,\(1\le n,q\le 10^5,1\le m\le n\)。
讲解
我们有一个大的思路,连续段数等于总亮灯数减去相邻两盏灯都开着的对数。(我竟然想分三类情况讨论,人直接傻掉)
我们称出现次数大于根号级别的路灯为大路灯,反之成为小路灯。
这不就很好做了吗,考虑分块,我们对大路灯预处理出互相之间的影响,然后在操作中可以轻松维护小路灯和大路灯对大路灯的贡献影响。
而小路灯只需要暴力做即可。
时间复杂度 \(O(n\sqrt{n})\)
代码
//12252024832524
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int MAXB = 320;
int n,m,Q;
int c[MAXN],cnt[MAXN],ID[MAXN],IDtot;
vector<int> pos[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
bool vis[MAXN];
int xd[MAXB],dd[MAXB],add[MAXB][MAXB];
int main()
{
// freopen("light.in","r",stdin);
// freopen("light.out","w",stdout);
n = Read(); m = Read(); Q = Read();
for(int i = 1;i <= n;++ i)
{
c[i] = Read();
if(c[i] == c[i-1]) i--,n--;
else cnt[c[i]]++;
}
int B = sqrt(n);
for(int i = 1;i <= m;++ i)
if(cnt[i] >= B) ID[i] = ++IDtot;
for(int i = 1;i <= n;++ i)
{
pos[c[i]].push_back(i);
if(i > 1 && ID[c[i]] && ID[c[i-1]]) add[ID[c[i]]][ID[c[i-1]]]++,add[ID[c[i-1]]][ID[c[i]]]++;
}
int S = 0,ad = 0;//sum & adjacent
while(Q--)
{
int clr = Read();
vis[clr] ^= 1;
if(vis[clr])//
{
S += cnt[clr];
if(ID[clr])
{
ad += xd[ID[clr]] + dd[ID[clr]];
for(int i = 1;i <= IDtot;++ i)
if(i != ID[clr])
dd[i] += add[ID[clr]][i];
}
else
{
for(int i = 0,len = pos[clr].size();i < len;++ i)
{
int now = pos[clr][i];
if(now > 1)
{
if(vis[c[now-1]]) ad++;
if(ID[c[now-1]]) xd[ID[c[now-1]]]++;
}
if(now < n)
{
if(vis[c[now+1]]) ad++;
if(ID[c[now+1]]) xd[ID[c[now+1]]]++;
}
}
}
}
else
{
S -= cnt[clr];
if(ID[clr])
{
ad -= xd[ID[clr]] + dd[ID[clr]];
for(int i = 1;i <= IDtot;++ i)
if(i != ID[clr])
dd[i] -= add[ID[clr]][i];
}
else
{
for(int i = 0,len = pos[clr].size();i < len;++ i)
{
int now = pos[clr][i];
if(now > 1)
{
if(vis[c[now-1]]) ad--;
if(ID[c[now-1]]) xd[ID[c[now-1]]]--;
}
if(now < n)
{
if(vis[c[now+1]]) ad--;
if(ID[c[now+1]]) xd[ID[c[now+1]]]--;
}
}
}
}
Put(S - ad,'\n');
}
return 0;
}