P14598

x_plus_b · 2025-11-24 20:48:43 · 题解

感觉是极简做法。

首先单调增和单调减没区别，所以考虑从左到右做。

一个显然的朴素贪心是前面有异色的就放在异色的，没有异色的就另开一行，对每个询问开两个大根堆维护，这样就能解决 task 1 和 2 了。

接下来考虑这样一个结论：如果在做一个询问 [1,n] 中积木 i 和 j 放在一起，那么在其他任何包含 i,j 的询问中 i 和 j 堆在一起一定不劣。更具体的，可以给每个 i 匹配一个下标最大的未被匹配的异色积木 pre_i。在一次询问跳到 i 时，把 i 放在 pre_i (如果同存在于询问区间) 上一定不劣。（如果 pre_i 不存在于询问区间则新开一个塔）。

::::info[一个可能并不严谨的证明] 考虑我们的朴素贪心，每个积木必须有异色就放在先前的异色积木，否则新开一个塔。那么反证法，假设在这种贪心策略下有一个积木 i 在前面有异色积木的情况下依旧新开一行。

首先如果 pre_i \geq l，因为我们对 pre_i 的定义所以肯定没有一个 j \in [l, i - 1] 使 pre_j = pre_i，因此 pre_i 上肯定没有新的积木，按照我们刚刚的策略会直接放在 pre_i 上，不符合假设。

否则如果 pre_i < l，且 [l, i-1] 上存在一个异色积木没有被搭上，设该积木为 j，那么肯定在 [j + 1, i - 1] 中不存在任何一个 k 使 pre_k = j（否则就会被搭上），那么根据 pre_i 的定义，i 一定会优先选取 j 而非当前的 pre_i，也矛盾。

因此该结论是正确的。 ::::

然后就简单了，i 和 pre_i 肯定放在一个塔上，你把塔看成颜色，就变成了区间数颜色数，这是一个典题，把询问离线挂在右端点上树状数组维护即可。

时间复杂度: O(n \log n)。

::::info[code]

#include <bits/stdc++.h>

using namespace std;

#define N 100005

int n, q, l, r;
int pre[N], ans[N];
char col[N];
priority_queue<int> q1, q2;

struct Query {
    int idx, l;
};

vector <Query> v1[N];

#define lowbit(i) (i & (-i))

struct BIT {
    int tree[N];
    void modify (int t, int val) {
        for (int i = t; i <= n; i += lowbit (i))
            tree[i] += val;
    }
    int sum (int t) {
        int res = 0;
        for (int i = t; i; i -= lowbit (i))
            res += tree[i];
        return res;
    }
    int query (int l, int r) {
        return sum (r) - sum (l - 1);
    }
}B1;

int main () {
    scanf ("%d%d", &n, &q);
    scanf ("%s", col + 1);
    for (int i = 1; i <= n; i++) {
        if (col[i] == 'P') {
            if (q1.size ()) {
                pre[i] = q1.top ();
                q1.pop ();
            }
            q2.push (i);
        } else {
            if (q2.size ()) {
                pre[i] = q2.top ();
                q2.pop ();
            }
            q1.push (i);
        }
    }
    for (int i = 1; i <= q; i++) {
        scanf ("%d%d", &l, &r);
        v1[r].push_back ({i, l});
    }
    for (int i = 1; i <= n; i++) {
        if (pre[i]) B1.modify (pre[i], -1);
        B1.modify (i, 1);
        for (auto && cur : v1[i]) 
            ans[cur.idx] = B1.query (cur.l, i);
    }
    for (int i = 1; i <= q; i++) printf ("%d\n", ans[i]);
}

::::