专栏文章

P14598

xx_plus_b
P14598题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@min19i4m
此快照首次捕获于
2025/12/01 18:55
3 个月前
此快照最后确认于
2025/12/01 18:55
3 个月前
查看原文
感觉是极简做法。
首先单调增和单调减没区别，所以考虑从左到右做。
一个显然的朴素贪心是前面有异色的就放在异色的，没有异色的就另开一行，对每个询问开两个大根堆维护，这样就能解决 task 1 和 2 了。
接下来考虑这样一个结论：如果在做一个询问 [1,n][1,n] 中积木 ii 和 jj 放在一起，那么在其他任何包含 i,ji,j 的询问中 ii 和 jj 堆在一起一定不劣。更具体的，可以给每个 ii 匹配一个下标最大的未被匹配的异色积木 preipre_i。在一次询问跳到 ii 时，把 ii 放在 preipre_i (如果同存在于询问区间) 上一定不劣。（如果 preipre_i 不存在于询问区间则新开一个塔）。
一个可能并不严谨的证明
考虑我们的朴素贪心，每个积木必须有异色就放在先前的异色积木，否则新开一个塔。那么反证法，假设在这种贪心策略下有一个积木 ii 在前面有异色积木的情况下依旧新开一行。
首先如果 prei≥lpre_i \geq l，因为我们对 preipre_i 的定义所以肯定没有一个 j∈[l,i−1]j \in [l, i - 1] 使 prej=preipre_j = pre_i，因此 preipre_i 上肯定没有新的积木，按照我们刚刚的策略会直接放在 preipre_i 上，不符合假设。
否则如果 prei<lpre_i < l，且 [l,i−1][l, i-1] 上存在一个异色积木没有被搭上，设该积木为 jj，那么肯定在 [j+1,i−1][j + 1, i - 1] 中不存在任何一个 kk 使 prek=jpre_k = j（否则就会被搭上），那么根据 preipre_i 的定义，ii 一定会优先选取 jj 而非当前的 preipre_i，也矛盾。
因此该结论是正确的。
然后就简单了，ii 和 preipre_i 肯定放在一个塔上，你把塔看成颜色，就变成了区间数颜色数，这是一个典题，把询问离线挂在右端点上树状数组维护即可。
时间复杂度: O(nlog⁡n)O(n \log n)。
codeCPP
#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]);
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...