[AGC059A] My Last ABC Problem

Genius_Star · 2026-09-04 08:17:55 · 题解

或许更好的阅读体验。

好好好，喜欢对脑电波。

思路：

首先可以将相同字符缩成一段，那么每次操作 [l, r] 时可以将 l 和 r 分别变成和 s_{l - 1}, s_{r + 1} 相同的字符，那就可以合并了，相当于删除了两个字符。

而显然的，一次最多删两个字符，至少可以删一个，因为可能 s_l = s_r 且 s_{l - 1} \ne s_{r + 1} 或者 s_{l - 1} = s_{r + 1} 且 s_l \ne s_r；事实证明，对于一个长度 n \ge 5 的字符串，一定可以找到 l, r 满足 s_l = s_r 或者 s_{l - 1} = s_{r + 1}（此时可以删两个），这是显然的。

当 n = 4 的时候，手摸一下，发现答案恰好是 2，于是偶数时答案是 \frac{n}{2}。

否则，最后剩下 n = 3 的时候，显然最后只剩下 s_1, s_i, s_n（因为前面删不掉 s_1, s_n），于是需要判断 s_1 与 s_n 是否相同即可，相同的话直接操作中间的 s_i，否则要操作两次；所以应该是 \frac{n - 3}{2} + 1 + [s_1 \ne s_n] = \lceil \frac{n - 1 + [s_1 \ne s_n]}{2} \rceil。

但是这还是把整个段相同字符缩在一起的长度，对于区间 [l, r]，考虑 [s_i \ne s_{i - 1}] 时代表了一个段的开头，于是预处理 [s_i \ne s_{i - 1}] 的前缀和 S，则区间 [l, r] 缩段后的长度为 S_r - S_l + 1。

于是时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, q, l, r;
int S[N];
char s[N];
int main(){
    n = read(), q = read();
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i)
      S[i] = S[i - 1] + (s[i] != s[i - 1]);
    while(q--){
        l = read(), r = read();
        int len = S[r] - S[l] + 1;
        if(len == 1){
            puts("0");
            continue;
        }
        if(len & 1)
          write(((len - 1) >> 1) + (s[l] != s[r]));
        else
          write(len >> 1);
        putchar('\n');
    }
    return 0;
}