No Time to Paint

题意

给定长度为 $N$ 的目标颜色字符串，颜色从浅到深为 A 到 Z。

一次操作可以选择一个连续区间，把它刷成同一种颜色；但不能在更深的颜色上覆盖更浅的颜色。

每个询问给出一个区间 $[a,b]$ ，表示这一段不刷。要把区间左侧和右侧刷成目标颜色，问最少需要多少笔。

思路

先看一个朴素做法：每个询问都重新计算左段和右段分别需要多少笔。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:07
 * update_at: 2026-07-11 20:08
 */
// brute.cpp：小数据暴力解，每个询问重新扫描左右两段。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, q;
string s;

// 计算 s[l..r] 这一段单独刷成目标颜色需要的最少笔数。
int count_segment(int l, int r) {
    stack<char> st;
    int cnt = 0;
    for (int i = l; i <= r; i++) {
        char c = s[i];
        while (!st.empty() && st.top() > c) {
            st.pop();
        }
        if (st.empty() || st.top() < c) {
            st.push(c);
            cnt++;
        }
    }
    return cnt;
}

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

    cin >> n >> q;
    cin >> s;
    s = " " + s;

    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        int left_need = count_segment(1, a - 1);
        int right_need = count_segment(b + 1, n);
        cout << left_need + right_need << '\n';
    }

    return 0;
}

这个暴力的核心子问题是：给定一个连续字符串，最少需要几笔把它刷出来。

官方解析使用一个很自然的栈模型。我们从左到右扫描颜色，栈里保存“当前还没结束的刷漆层”，并且从栈底到栈顶颜色逐渐变深。

遇到一个颜色 c 时：

如果栈顶颜色比 c 深，说明更深的那一笔必须在当前位置之前结束，把它弹掉；
弹完后，如果栈顶正好是 c，当前位置可以接在已有这一笔上；
如果栈为空，或者栈顶比 c 浅，就必须新开一笔颜色 c。

例如扫描 ABBA：

位置	颜色	操作	栈状态	已开笔数
1	`A`	新开 `A`	`A`	1
2	`B`	新开 `B`	`AB`	2
3	`B`	接着已有 `B`	`AB`	2
4	`A`	弹掉 `B`，接着已有 `A`	`A`	2

这张表的关键是第 4 行：B 比 A 深，不能跨过当前位置继续存在，否则当前位置会被刷成 B。所以 B 这一笔必须结束。

有了这个单段算法，询问 $[a,b]$ 就很简单了。中间区间不刷，任何一笔都不能跨过这个空白区间，所以答案等于：

\text{前 }a-1\text{ 段需要的笔数}+\text{后 }b+1\ldots N\text{ 段需要的笔数}

于是预处理：

prefix_cnt[i]：前 $i$ 段最少需要多少笔；
suffix_cnt[i]：第 $i$ 段到第 $N$ 段最少需要多少笔。

前缀从左到右扫一遍，后缀从右到左扫一遍，使用同一个栈规则。

每个询问直接输出：

prefix\_cnt[a-1]+suffix\_cnt[b+1]

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:07
 * update_at: 2026-07-11 20:08
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, q;
string s;
int prefix_cnt[MAXN]; // prefix_cnt[i] 表示前 i 段栅栏最少需要多少笔
int suffix_cnt[MAXN]; // suffix_cnt[i] 表示第 i..n 段栅栏最少需要多少笔

// 把颜色 c 加入当前扫描段，必要时开启一笔新的颜色。
void add_color(stack<char> &st, char c, int &cnt) {
    while (!st.empty() && st.top() > c) {
        st.pop();
    }
    if (st.empty() || st.top() < c) {
        st.push(c);
        cnt++;
    }
}

void build_prefix() {
    stack<char> st;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        add_color(st, s[i], cnt);
        prefix_cnt[i] = cnt;
    }
}

void build_suffix() {
    stack<char> st;
    int cnt = 0;
    for (int i = n; i >= 1; i--) {
        add_color(st, s[i], cnt);
        suffix_cnt[i] = cnt;
    }
}

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

    cin >> n >> q;
    cin >> s;
    s = " " + s;

    build_prefix();
    build_suffix();

    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        cout << prefix_cnt[a - 1] + suffix_cnt[b + 1] << '\n';
    }

    return 0;
}

复杂度

预处理前缀和后缀各扫描一遍，每个颜色最多入栈、出栈常数次。

时间复杂度为 $O(N+Q)$ 。

空间复杂度为 $O(N)$ 。

总结

本题的关键是把刷漆过程看成“浅色在下，深色在上”的栈结构。

删除一个区间后，左右两边无法用同一笔跨过去，因此可以独立计算。前后缀预处理把暴力中每次重复扫描的部分消掉，查询就变成一次加法。

目录

题意

思路

代码

复杂度

总结