P12246 电 van 题解

Mier_Samuelle · 2025-04-19 16:02:21 · 题解

首先，对于一个确定的字符串 s，考虑如何求出现次数。

显然，先处理出每个前缀中 \texttt{v} 的数量，和每个后缀中 \texttt{n} 的数量，然后对于每个 \texttt{a} 分别计算贡献即可。

不难发现，对于每次操作，只有 s_x 和 s_{x+1} 的贡献发生了改变，故只需考虑这两个位置。

单次询问时间复杂度 O(1)，预处理复杂度 O(n)，总复杂度 O(n+q)。

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