S 组模拟赛 题解汇总

---

T1 标注逗号

题意

给定长度为 $n$ 的数字串 $s$ 和正整数 $k$，要求从右往左每 $k$ 位插入一个逗号，最高位前不能有逗号。

思路

子任务 1（$n\le 1000$）

直接模拟：从右往左找到每个需要插入逗号的位置，用 string::insert 插入。单次插入是 $O(n)$，最多插入 $O(n)$ 次，总复杂度 $O(n^2)$。

子任务 2（$n\le 10^6$）

反复插入太慢，考虑直接构造答案。

从左往右扫描，设当前处理到下标 $i$（从 $0$ 开始）。当前位及其右边一共有 $n-i$ 位。如果 $i>0$ 且 $n-i$ 是 $k$ 的倍数，说明从右往左分组时，$s_i$ 是一个新组的开头，需要在它前面加一个逗号。

否则直接输出 $s_i$。这样每个字符只处理一次。

正确性证明

任意一个逗号只能出现在两个相邻字符之间。考虑 $s_{i-1}$ 和 $s_i$ 之间的边界，它右边一共有 $n-i$ 位。

从右往左每 $k$ 位分组，分界点恰好出现在距离右端 $k,2k,3k,\dots$ 的位置。因此这个边界需要加逗号，当且仅当 $n-i$ 是 $k$ 的倍数。

另外 $i=0$ 时不能加逗号，否则会出现前导逗号。所以条件为：

$$i>0\quad\text{且}\quad (n-i)\bmod k=0$$

该条件既充分又必要，且每个字符只被加入答案一次，因此算法正确。

复杂度

时间复杂度 $O(n)$，空间复杂度 $O(n)$（答案串）。

参考代码

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

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

    int n, k;
    string s;
    cin >> n >> k >> s;

    string ans;
    ans.reserve(n + n / k + 5);

    for (int i = 0; i < n; ++i) {
        if (i > 0 && (n - i) % k == 0) {
            ans.push_back(',');
        }
        ans.push_back(s[i]);
    }

    cout << ans << '\n';
    return 0;
}

---

T2 数位删减

题意

给定 $n$ 个正整数。对每个数，必须删去恰好一个数位，并选择使删除后结果最小的数位。个位数删去后变成 $0$，删除后允许出现前导零。

设第 $i$ 个数删除后得到 $b_i$，令 $c_i=a_i-b_i$。将所有 $c_i$ 从大到小排序，按这个顺序依次执行删除，输出每次删除后所有数的总和。若多个 $c_i$ 相同，任意顺序处理即可，每次输出结果不变。

思路

子任务 1（$n\le 10$）

直接模拟：每一轮在尚未处理的数中找到 $c_i$ 最大的一个，执行删除，然后重新计算总和。数据范围很小，怎样实现都可以通过。

子任务 2（$a_i\le 99$）

每个数最多两位，只有两种删法：

• 删掉十位，剩下个位；
• 删掉个位，剩下十位。

分别算出结果，取较小的那个作为 $b_i$。之后同样按 $c_i$ 从大到小排序并依次输出。

子任务 3（完整数据）

对每个数独立求最优删除。把 $a_i$ 转成字符串，枚举删掉哪一位，把剩下的数字按十进制重新计算。删除后允许前导零，例如 100 删掉 1 得到 00，值为 $0$。

得到每个数的 $b_i$ 后，令 $c_i=a_i-b_i$。因为每个数恰好删除一次，且不同数之间互不影响，所以执行若干次删除后，总和等于：

$$\text{初始总和}-\sum_{\text{已删除的数}} c_i$$

把 $c_i$ 从大到小排序，依次减去并输出，即可得到题目要求的每一步结果。

正确性证明

第一步：$b_i$ 是最优结果。
枚举了所有可能的删除位置，因此得到的 $b_i$ 一定是删去一个数位后能得到的最小值。

第二步：排序后依次删除是正确的。
所有 $c_i$ 在删除前已经确定，且删除某个数不会影响其他数的 $c_j$。因此执行 $j$ 次删除后，总和只取决于“删除了哪 $j$ 个数”，与删除的先后顺序无关。

题目要求按 $c_i$ 从大到小删除，所以执行 $j$ 次后，被删除的正是 $c_i$ 最大的 $j$ 个数。维护当前总和，每次减去当前最大的 $c_i$，就得到了正确的输出。

若存在相同的 $c_i$，它们对总和的贡献相同，交换顺序不会改变任何一步的前缀和，因此任意顺序都可以。

复杂度

设每个数的位数为 $d$，则 $d\le 10$。

• 求所有 $b_i$：$O(n d^2)$；
• 排序：$O(n\log n)$。

总时间复杂度 $O(n d^2+n\log n)$，空间复杂度 $O(n)$。

参考代码

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

using ll = long long;

int best_remove(int x) {
    string s = to_string(x);
    int ans = x;

    for (int del = 0; del < (int)s.size(); ++del) {
        int v = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            if (i == del) continue;
            v = v * 10 + (s[i] - '0');
        }
        ans = min(ans, v);
    }

    return ans;
}

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    ll sum = 0;
    vector<int> reduce(n);

    for (int i = 0; i < n; ++i) {
        sum += a[i];
        reduce[i] = a[i] - best_remove(a[i]);
    }

    sort(reduce.begin(), reduce.end(), greater<int>());

    for (int i = 0; i < n; ++i) {
        sum -= reduce[i];
        cout << sum << '\n';
    }

    return 0;
}

---

T3 地铁通道

题意

通道被分成 $n$ 段，第 $i$ 段连接点 $i-1$ 和点 $i$。每个点的高度只能是 $1$ 或 $2$。

• 若 $s_i=1$，第 $i$ 段必须满足两端高度都为 $2$，花费 $a$。
• 若 $s_i=0$，第 $i$ 段两端可以任取 $1$ 或 $2$；两端相同花费 $a$，不同花费 $2a$。
• 点 $i$ 处需要焊接，高度 $1$ 花费 $b$，高度 $2$ 花费 $c$。

求最小总花费。

思路

子任务 1（$n\le 20$）

直接枚举所有 $h_0,h_1,\dots,h_n$ 的 $2^{n+1}$ 种取值，检查每段是否满足 $s_i=1$ 的限制，累加通道和焊接费用，取最小值。

子任务 2（所有 $s_i=0$）

所有段都没有高度限制。

• 全部建在高度 $1$：通道花费 $na$，焊接花费 $(n+1)b$，总计 $na+(n+1)b$。
• 全部建在高度 $2$：通道花费 $na$，焊接花费 $(n+1)c$，总计 $na+(n+1)c$。

如果高度既有 $1$ 又有 $2$，那么至少存在一次折线，通道花费至少为 $na+a$。焊接费用为 $xb+yc$，其中 $x+y=n+1$，所以它不会小于 $(n+1)\min(b,c)$。

因此混合方案的花费至少为：

$$na+a+(n+1)\min(b,c)$$

它严格大于全部建在较便宜高度上的花费：

$$na+(n+1)\min(b,c)$$

所以最优方案一定是全选高度 $1$ 或全选高度 $2$，答案为两者的较小值。

子任务 3（完整数据）

设 $f_{i,0}$ 表示处理完前 $i$ 段，且点 $i$ 的高度为 $1$ 时的最小花费；$f_{i,1}$ 表示点 $i$ 的高度为 $2$ 时的最小花费。

初始时点 $0$ 只有焊接费用：

$$f_{0,0}=b,\qquad f_{0,1}=c$$

考虑第 $i$ 段：

若 $s_i=1$：
两端都必须是高度 $2$，所以只能从 $f_{i-1,1}$ 转移：

$$f_{i,1}=f_{i-1,1}+a+c,\qquad f_{i,0}=+\infty$$

若 $s_i=0$：
第 $i$ 段可以从高度 $1$ 或 $2$ 出发，到达高度 $1$ 或 $2$。同高度花费 $a$，换高度花费 $2a$，再加上点 $i$ 的焊接费用：

$$\begin{aligned} f_{i,0}&=\min(f_{i-1,0}+a,\ f_{i-1,1}+2a)+b\\ f_{i,1}&=\min(f_{i-1,1}+a,\ f_{i-1,0}+2a)+c \end{aligned} $$

答案为 $\min(f_{n,0},f_{n,1})$。

正确性证明

对 $i$ 归纳证明：$f_{i,0}$ 和 $f_{i,1}$ 分别等于“处理完前 $i$ 段，且点 $i$ 高度固定为 $1$ 或 $2$”时的最小花费。

• $i=0$ 时没有通道，只有点 $0$ 的焊接费用，初始化正确。
• 若 $s_i=1$，第 $i$ 段强制两端高度为 $2$，点 $i$ 也只能是高度 $2$。最优方案必须从点 $i-1$ 高度为 $2$ 的状态转移，并支付通道费用 $a$ 和点 $i$ 的焊接费用 $c$，转移正确。
• 若 $s_i=0$，点 $i-1$ 和点 $i$ 的高度都可以是 $1$ 或 $2$。枚举两种前一状态，按“同高度 $a$、不同高度 $2a$”支付通道费用，再加上点 $i$ 的焊接费用，取最小值，转移正确。

因此归纳成立，最终答案取点 $n$ 两种高度的较小值即可。

复杂度

时间复杂度 $O(n)$，使用滚动变量后空间复杂度 $O(1)$。

参考代码

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

using ll = long long;

const ll INF = (1LL << 60);

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

    int n;
    ll a, b, c;
    string s;
    cin >> n >> a >> b >> c >> s;

    ll f0 = b;
    ll f1 = c;

    for (int i = 0; i < n; ++i) {
        ll g0, g1;

        if (s[i] == '1') {
            g0 = INF;
            g1 = f1 + a + c;
        } else {
            g0 = min(f0 + a, f1 + 2 * a) + b;
            g1 = min(f1 + a, f0 + 2 * a) + c;
        }

        f0 = g0;
        f1 = g1;
    }

    cout << min(f0, f1) << '\n';
    return 0;
}

---

T4 目录校验

题意

给定若干组“父目录—子文件”关系，以及要求的题目文件夹数量 $m$。判断每组目录是否符合以下格式：

1. 根目录只能有一个，名称必须由至少一个字母后面接至少一个数字组成，字母在前、数字在后，不能有其他字符。
2. 根目录下必须恰有 $m$ 个题目文件夹，名称只能由字母组成。
3. 每个题目文件夹中必须恰有一个 .cpp 文件，文件名必须等于文件夹名加上 .cpp。
4. 只判断文件名，不判断文件类型。即 task.cpp 可以是一个文件夹，但它不能再包含任何子文件。
5. 不能有多余的文件或目录，所有给出的节点必须构成一棵以根目录为根的树。

输入可能不合法，例如一个节点有多个父亲、存在环、存在多个根等，这些情况都判为不合法。

思路

建图

把每个不同的名字看成一个节点，每条关系 $A\to B$ 看成一条有向边，表示 $B$ 是 $A$ 的子文件或子目录。

同时维护：

• indeg[v]：节点 $v$ 的父亲数量；
• child[u]：节点 $u$ 的所有孩子；
• name[i]：编号为 $i$ 的节点的名字。

合法结构的必要条件

一个合法目录固定包含：

• $1$ 个根目录；
• $m$ 个题目文件夹；
• $m$ 个 .cpp 文件。

所以合法时：

• 节点数一定是 $1+2m$；
• 关系数一定是 $2m$。

读入后如果节点数或关系数不对，可以直接输出 no。

检查步骤

1. 每个节点最多一个父亲。
   如果某个节点在加入边时已经有父亲，说明它被多个目录包含，不合法。

2. 根唯一。
   入度为 $0$ 的节点必须恰好有一个，作为根。

3. 根名合法。
   先读若干字母，再读若干数字，两段都必须非空，并且读完数字后必须到达字符串结尾。

4. 所有节点从根可达。
   从根开始 BFS/DFS，访问到的节点数必须等于总节点数。否则存在环、游离节点或多个连通块。

5. 根的孩子数量与名字。
   根必须恰有 $m$ 个孩子，且每个孩子的名字必须全部是字母。

6. 每个题目文件夹的孩子。
   每个题目文件夹必须恰有一个孩子，名字必须等于“文件夹名 + .cpp”，并且这个 .cpp 节点不能再有孩子。

所有检查都通过才输出 yes，否则输出 no。

正确性证明

必要性。
如果目录合法，它显然满足上述所有条件：根唯一且命名合法，根下恰有 $m$ 个纯字母文件夹，每个文件夹恰有一个同名的 .cpp 子节点，.cpp 节点没有孩子，并且所有节点构成一棵以根为根的树。

充分性。
假设所有检查通过。

• 每个节点入度不超过 $1$，且 BFS 能从根到达所有节点，所以除根以外每个节点恰好有一个父亲。因此图是一棵以根为根的有向树，不存在环，也不存在游离节点。
• 根恰有 $m$ 个孩子，每个孩子恰有一个孩子，且这个孩子名为“文件夹名 + .cpp”并且没有孩子。
• 由于所有节点都从根可达，树的节点只能是：根、$m$ 个题目文件夹、$m$ 个 .cpp 文件，共 $1+2m$ 个。因此不会出现第四层，也不会有多余文件或目录。
• 根名和文件夹名的格式检查也都通过。

所以该目录完全符合题目要求，输出 yes 是正确的。

复杂度

使用哈希表给名字编号，单组数据的期望时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

参考代码

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

bool is_root_name(const string &s) {
    int i = 0;
    int n = (int)s.size();

    while (i < n && isalpha((unsigned char)s[i])) ++i;
    if (i == 0 || i == n) return false;

    while (i < n && isdigit((unsigned char)s[i])) ++i;
    return i == n;
}

bool all_letters(const string &s) {
    if (s.empty()) return false;

    for (char c : s) {
        if (!isalpha((unsigned char)c)) return false;
    }

    return true;
}

void solve() {
    int n, m;
    cin >> n >> m;

    unordered_map<string, int> id;
    id.reserve(2 * m + 5);

    vector<string> name;
    vector<vector<int>> child;
    vector<int> indeg;

    auto get_id = [&](const string &s) -> int {
        auto it = id.find(s);
        if (it != id.end()) return it->second;

        int x = (int)name.size();
        id[s] = x;
        name.push_back(s);
        child.push_back({});
        indeg.push_back(0);
        return x;
    };

    bool bad = false;

    for (int i = 0; i < n; ++i) {
        string A, B;
        cin >> A >> B;

        int u = get_id(A);
        int v = get_id(B);

        if (indeg[v] > 0) {
            bad = true;
            continue;
        }

        ++indeg[v];
        child[u].push_back(v);
    }

    int node_count = (int)name.size();

    // 合法目录必须有 2m 条关系和 2m+1 个节点
    if (bad || n != 2 * m || node_count != 2 * m + 1) {
        cout << "no\n";
        return;
    }

    int root = -1;
    int roots = 0;

    for (int i = 0; i < node_count; ++i) {
        if (indeg[i] == 0) {
            root = i;
            ++roots;
        }
    }

    if (roots != 1 || !is_root_name(name[root])) {
        cout << "no\n";
        return;
    }

    vector<int> vis(node_count, 0);
    queue<int> q;
    q.push(root);
    vis[root] = 1;

    int visited = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++visited;

        for (int v : child[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }

    if (visited != node_count) {
        cout << "no\n";
        return;
    }

    if ((int)child[root].size() != m) {
        cout << "no\n";
        return;
    }

    for (int folder : child[root]) {
        if (!all_letters(name[folder]) || (int)child[folder].size() != 1) {
            cout << "no\n";
            return;
        }

        int file = child[folder][0];

        if (name[file] != name[folder] + ".cpp" || !child[file].empty()) {
            cout << "no\n";
            return;
        }
    }

    cout << "yes\n";
}

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

    int T;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

---

T5 众数区间

题意

给定长度为 $n$ 的整数数组 $a$ 和正整数 $k$。对于一个连续子数组，定义它的众数出现次数为其中出现次数最多的数的出现次数。

求有多少个连续子数组的众数出现次数不小于 $k$。

思路

子任务 1（$n\le 1000$）

枚举左端点 $l$，右端点 $r$ 从 $l$ 开始向右扩展，用桶维护每个数的出现次数和当前最大出现次数。

如果最大出现次数达到 $k$，那么当前区间以及所有右端点更大的区间都满足条件，可以直接加上 $n-r+1$ 并结束当前左端点的枚举。

复杂度 $O(n^2)$。

子任务 2（$k=1$）

任何非空子数组都至少有一个数出现 $1$ 次，所以所有非空子数组都满足条件。

答案为：

$$\frac{n(n+1)}{2}$$

子任务 3（完整数据）

不需要真的求众数。一个区间满足条件，当且仅当区间内存在某个数出现至少 $k$ 次。

固定右端点 $r$。对于每个出现过至少 $k$ 次的值 $x$，设它在 $[1,r]$ 中的出现位置为：

$$p_1<p_2<\cdots<p_t$$

那么第 $k$ 个“从右往左数”的出现位置是 $p_{t-k+1}$，也就是数组下标中的 pos[x].size() - k（从 $0$ 开始编号）。

记这个位置为 $q_x$。那么区间 $[l,r]$ 中至少包含 $k$ 个 $x$，当且仅当：

$$l\le q_x$$

因为：

• 若 $l\le q_x$，则 $q_x$ 以及它右边的 $k-1$ 个 $x$ 都在区间内，共 $k$ 个；
• 若 $l>q_x$，则 $q_x$ 左边被截掉，区间内最多只剩 $k-1$ 个 $x$。

因此，区间 $[l,r]$ 满足条件，当且仅当存在某个 $x$ 使得 $l\le q_x$，等价于：

$$l\le \max_x q_x$$

设 left = max q_x。那么以 $r$ 结尾的合法子数组个数恰好是 left，因为左端点可以取 $1,2,\dots,\text{left}$。

在线维护：

• 读入 $a_r=x$，把 $r$ 加入 pos[x]；
• 如果 pos[x].size() >= k，令 $q_x$ 为 pos[x][pos[x].size() - k]；
• 更新 left = max(left, q_x)；
• 答案累加 left。

为什么只需要用新的 $q_x$ 更新一次？因为当前右端点只让 $x$ 的出现位置列表发生变化，其他数的 $q_y$ 没有变化。因此新的最大值就是“旧最大值”和“新的 $q_x$”的较大值。

正确性证明

引理 1： 对固定的 $r$ 和值 $x$，区间 $[l,r]$ 中至少包含 $k$ 个 $x$，当且仅当 $l\le q_x$。

证明：$q_x$ 是 $x$ 在 $[1,r]$ 中从右往左数的第 $k$ 个出现位置。若 $l\le q_x$，则 $q_x$ 及其右边的 $k-1$ 个 $x$ 都在 $[l,r]$ 中，至少有 $k$ 个；若 $l>q_x$，则 $q_x$ 不在区间中，最多只能包含它右边的 $k-1$ 个 $x$。

引理 2： 区间 $[l,r]$ 满足条件，当且仅当 $l\le \max_x q_x$。

证明：区间满足条件，等价于存在某个 $x$ 出现至少 $k$ 次，等价于存在某个 $x$ 满足 $l\le q_x$，等价于 $l\le \max_x q_x$。

由引理 2，固定 $r$ 时，合法左端点恰好是 $1,2,\dots,\text{left}$，共 left 个。

算法按 $r$ 从小到大处理，每次只更新当前值 $x$ 的 pos[x] 和 $q_x$，其他值的 $q_y$ 不变，因此用 left = max(left, q_x) 就能得到当前所有 $q$ 的最大值。答案按右端点分类累加，每个合法子数组恰好被统计一次。

复杂度

每个元素只会被加入一次出现位置列表，哈希表操作期望 $O(1)$。

• 期望时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$。

参考代码

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

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

    int n, k;
    cin >> n >> k;

    unordered_map<int, vector<int>> pos;
    pos.max_load_factor(0.7);
    pos.reserve(n * 2);

    long long left = 0;
    long long ans = 0;

    for (int r = 1; r <= n; ++r) {
        int x;
        cin >> x;

        vector<int> &v = pos[x];
        v.push_back(r);

        if ((int)v.size() >= k) {
            int q = v[(int)v.size() - k];
            left = max(left, (long long)q);
        }

        ans += left;
    }

    cout << ans << '\n';
    return 0;
}

---

T6 重排代价

题意

给定一个长度为 $n$ 的排列 $a$，以及两个整数 $L,R$。

一次操作可以选出一个元素，把它取出并插入到序列的任意位置。只有权值在 $[L,R]$ 内的元素允许不被操作；权值不在 $[L,R]$ 内的元素必须至少被操作一次。

求把排列变成递增排列的最少操作次数。

思路

关键观察

没有被操作过的元素，它们之间的相对顺序不会改变。最终排列是递增的，所以这些“不动元素”在原序列中也必须按值递增出现。

反过来，只要选出的不动元素在原序列中按值递增，就可以保持它们不动，把其他元素各移动一次完成排序。

因此，问题转化为：

在所有权值属于 $[L,R]$ 的元素中，最多能留下多少个元素不动，使得它们在原序列中递增？

这就是把所有 $a_i\in[L,R]$ 按原顺序取出后，求最长上升子序列（LIS）的长度。

设这个长度为 len，答案为：

$$n-\text{len}$$

子任务 1（$n\le 10$）

枚举所有“保留哪些位置”的子集，检查保留下来的元素是否都在 $[L,R]$ 内，并且按原顺序严格递增。设最多能保留 $x$ 个，答案就是 $n-x$。

子任务 2（$R-L\le 1$）

筛选后最多只有两种数：$L$ 和 $R$（如果 $L=R$，则只有一种）。

• 若一种都没有，能保留 $0$ 个；
• 若只有一种，能保留 $1$ 个；
• 若两种都有，只有存在一个 $L$ 出现在某个 $R$ 之前时，才能同时保留 $L$ 和 $R$，即保留 $2$ 个；否则最多保留 $1$ 个。

答案同样是 $n-\text{保留个数}$。

子任务 3（完整数据）

只保留权值在 $[L,R]$ 内的元素，按原顺序形成一个新序列。对这个序列求 LIS：

• 维护一个数组 tails，其中 tails[i] 表示长度为 $i+1$ 的上升子序列的最小结尾值；
• 对于每个新元素 $x$，用 lower_bound 找到第一个不小于 $x$ 的位置并替换；
• 如果找不到，就把它追加到末尾。

tails 的长度就是 LIS 长度。

正确性证明

下界：操作次数至少是 $n-\text{LIS}$。
设没有被操作的元素集合为 $S$。这些元素在最终排列中仍然保持原来的相对顺序，而最终排列递增，所以 $S$ 在原序列中必须按值递增。并且 $S$ 中的元素权值都必须在 $[L,R]$ 内，因为区间外的元素必须被操作。

因此 $|S|$ 不超过“只考虑 $[L,R]$ 内元素时的 LIS 长度”，即：

$$|S|\le \text{LIS}$$

所以操作次数至少为 $n-\text{LIS}$。

上界：$n-\text{LIS}$ 次操作一定足够。
取一个长度为 $\text{LIS}$ 的上升子序列 $S$，保持 $S$ 中的元素不动。对于所有不在 $S$ 中的元素，按权值从小到大依次处理：把当前元素取出，插入到“已经确定位置的元素”中正确的位置。

因为处理顺序是权值递增，后处理的元素一定比已经处理的元素大，所以它只会被插入到后面，不会破坏已经确定好的相对顺序。最终所有元素按值递增排列，每个不在 $S$ 中的元素恰好被操作一次。

因此最多需要 $n-\text{LIS}$ 次操作。

上下界相同，答案为 $n-\text{LIS}$。

复杂度

LIS 使用二分维护，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

参考代码

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

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

    int n, L, R;
    cin >> n >> L >> R;

    vector<int> tails;
    tails.reserve(n);

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;

        // 区间外的元素必须移动，不能留在不动集合中
        if (x < L || x > R) continue;

        auto it = lower_bound(tails.begin(), tails.end(), x);

        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << n - (int)tails.size() << '\n';
    return 0;
}