题解：CF570C Replacement

lailai0916 · 2024-12-24 01:16:43 · 题解

题意简述

给定长度为 n 的字符串，包含 . 和小写字母，进行 m 次操作，每次修改一个字符，并询问将所有连续 . 转化为单个 . 所需的次数。

解题思路

设字符串中有 k 个连续的 . 子串，长度分别为 a_i。每个子串需要 a_i - 1 次转化，总转化次数为：

注意到，\sum_{i=1}^k a_i 为字符串中所有 . 的总数，在每次操作中，判断是否将某个 . 替换为字母或字母替换为 .，即可更新 . 的数量。

对于每次操作分类讨论，维护 . 子串数量：

1. 将 . 替换为字母：如果左右两边都是字母，则 . 子串数量减少 1，转化次数加 1；如果左右两边都是 .，则 . 子串数量增加 1，转化次数减少 1。
2. 将字母替换为 .：如果左右两边都是字母，则 . 子串数量增加 1，转化次数减少 1；如果左右两边都是 .，则 . 子串数量减少 1，转化次数增加 1。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=300005;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        char f;
        cin>>f;
        a[i]=f=='.';
        if(a[i]&&a[i-1])ans++;
    }
    while(m--)
    {
        int x;
        char f;
        cin>>x>>f;
        int y=f=='.';
        if(a[x]!=y)
        {
            a[x]=y;
            ans+=(a[x-1]+a[x+1])*(y*2-1);
        }
        cout<<ans<<'\n';
    }
    return 0;
}