题解：P12246 电 van

Azure_F · 2025-04-19 19:16:25 · 题解

分讨。

首先我们先 O(n) 地求出原本的子序列个数：

ll cv = 0ll, cva = 0ll, cvan = 0ll;
for(int i = 1; i <= n; ++i) {
    cv += (s[i - 1] == 'v');
    cva += cv * (s[i - 1] == 'a');
    cvan += cva * (s[i - 1] == 'n');
}

其中 cvan 即为答案。

接下来考虑我们更新答案时需要什么：

• 显然如果我们交换的是 \tt v, a，我们需要知道之后的 \tt n 的个数来对答案进行加减；
• 如果我们交换的是 \tt a, n，我们需要知道前面的 \tt v 的个数来进行加减；
• 如果我们交换的是 \tt v, n，不会对答案产生影响。

因此我们预处理两个数组 prev_v 和 next_n，含义如上表示：

for(int i = 1; i <= n; ++i) {
    prev_v[i] = prev_v[i - 1] + (s[i - 1] == 'v');
}
for(int i = n; i >= 1; --i) {
    next_n[i] = next_n[i + 1] + (s[i - 1] == 'n');
}

然后每次交换的时候更新一下两个数组和答案即可。

while(m--) {
    int x; std::cin >> x;
    if(s[x - 1] == 'v' && s[x] == 'n') --prev_v[x], --next_n[x + 1];
    if(s[x - 1] == 'n' && s[x] == 'v') ++prev_v[x], ++next_n[x + 1];
    if(s[x - 1] == 'v' && s[x] == 'a') --prev_v[x], cvan -= next_n[x];
    if(s[x - 1] == 'a' && s[x] == 'v') ++prev_v[x], cvan += next_n[x];
    if(s[x - 1] == 'a' && s[x] == 'n') --next_n[x + 1], cvan -= prev_v[x];
    if(s[x - 1] == 'n' && s[x] == 'a') ++next_n[x + 1], cvan += prev_v[x];
    std::swap(s[x - 1], s[x]); std::cout << cvan << "\n";
}