P12246 电 van 题解

首先，对于一个确定的字符串

s

，考虑如何求出现次数。

显然，先处理出每个前缀中

\texttt{v}

的数量，和每个后缀中

\texttt{n}

的数量，然后对于每个

\texttt{a}

分别计算贡献即可。

不难发现，对于每次操作，只有

s_x

和

s_{x+1}

的贡献发生了改变，故只需考虑这两个位置。

单次询问时间复杂度

O(1)

，预处理复杂度

O(n)

，总复杂度

O(n+q)

。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e6 + 10;
int pre[MAXN], suf[MAXN];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string str;
	int n, m;
	cin >> n >> m >> str;
	str = " " + str;
	int ans = 0;
	for (int i = 1;i <= n;i++) pre[i] = pre[i - 1] + (str[i] == 'v');
	for (int i = n;i >= 1;i--) suf[i] = suf[i + 1] + (str[i] == 'n');
	for (int i = 1;i <= n;i++) ans += (str[i] == 'a') * pre[i - 1] * suf[i + 1];
	while (m--){
		int x;
		cin >> x;
		ans -= (str[x] == 'a') * pre[x - 1] * suf[x + 1];
		ans -= (str[x + 1] == 'a') * pre[x] * suf[x + 2];
		swap(str[x], str[x + 1]);
		pre[x] = pre[x - 1] + (str[x] == 'v');
		pre[x + 1] = pre[x] + (str[x + 1] == 'v');
		suf[x + 1] = suf[x + 2] + (str[x + 1] == 'n');
		suf[x] = suf[x + 1] + (str[x] == 'n');
		ans += (str[x] == 'a') * pre[x - 1] * suf[x + 1];
		ans += (str[x + 1] == 'a') * pre[x] * suf[x + 2];
		cout << ans << endl;
	}
	return 0;
}

文章操作

相关推荐

评论

P12246 电 van 题解