CF 1609E William The Oblivious

题目描述

https://codeforces.com/contest/1609/problem/E

简要题意：给定一个字符串 $S$，该字符串只含有 $a,b,c$ 这三个字符，你现在可以修改任意次，每次可以将任意一个字母修改成 $a,b,c$ 这三个字符中的某一个，求最小修改多少次使得不存在 $abc$ 这样的子序列，同时现在有 $m$ 次询问，每次询问修改 $S$ 的一个字符，求最小修改次数

$|S|,m \le 10^5$

Solution

注意到信息满足可合并性，我们考虑线段树，用线段树维护 $a,b,c,ab,bc,abc$ 分别表示区间内不含有这些子序列的最小操作次数

考虑合并，容易得到 $a,b,c$ 的合并是直接相加，但对于 $ab$ 的合并似乎找不到合适的方法，我们考虑分类讨论，如果要使得左右区间合并后不存在 $ab$，那么在保证左右区间内部不含有 $ab$ 的情况下，只有两种情况，一是左边不含 $a$，二是右边不含 $b$，然后我们能够注意到左边不含 $a$ 则一定满足左边不含 $ab$，所以左边不含 $a$ 的情况就是 $T[lc].a + T[rc].ab$，那么容易得到第二种情况就是 $T[lc].ab+T[rc].b$，其它的类似都可以用这种方法得到

单点修改用线段树操作即可，时间复杂度 $O(n\log n)$

#include <iostream>
#include <algorithm>
#define maxn 100010
#define ll long long
#define INF 1000000000
using namespace std;

int n, m;
char s[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    int a, b, c, ab, bc, abc;
} T[maxn * 4];
inline Seg maintain(const Seg &ls, const Seg &rs) {
    Seg o;
    o.a = ls.a + rs.a;
    o.b = ls.b + rs.b;
    o.c = ls.c + rs.c;
    o.ab = min(ls.a + rs.ab, ls.ab + rs.b);
    o.bc = min(ls.b + rs.bc, ls.bc + rs.c);
    o.abc = min({ ls.abc + rs.c, ls.ab + rs.bc, ls.a + rs.abc });
    return o; 
}

void build(int i, int l, int r) {
    if (l == r) {
        T[i] = { 0, 0, 0, 0, 0, 0 };
        if (s[l] == 'a') T[i].a = 1;
        else if (s[l] == 'b') T[i].b = 1;
        else T[i].c = 1; return ;
    } int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    T[i] = maintain(T[lc], T[rc]);
}

void update(int i, int l, int r, int k, char ch) {
    if (l == r) {
        T[i] = { 0, 0, 0, 0, 0, 0 };
        if (ch == 'a') T[i].a = 1;
        else if (ch == 'b') T[i].b = 1;
        else T[i].c = 1; return ;
    } int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k, ch);
    else update(rc, m + 1, r, k, ch);
    T[i] = maintain(T[lc], T[rc]);
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> s + 1; build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int x; char c[3]; cin >> x >> c;
        update(1, 1, n, x, c[0]);
        cout << T[1].abc << "\n";
    }
    return 0;
}