专栏文章

题解：P9991 [Ynoi Easy Round 2023] TEST_107

CClaire0918
题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mionmoa1
此快照首次捕获于
2025/12/02 22:09
3 个月前
此快照最后确认于
2025/12/02 22:09
3 个月前
查看原文
要求值的类型比 [l,r][l, r] 少，考虑强制要求 [l,r][l, r] 中的一种值不能选。具体地，对于位置 ii，设上一个与其相等的位置为 preipre_i，下一个与其相等的位置为 nxtinxt_i，那么答案即为
max⁡i=lr{min⁡{i−l,i−prei−1},min⁡{r−i,nxti−i−1}}\max_{i = l}^{r} \{\min\{i - l, i - pre_i - 1\}, \min\{r - i, nxt_i - i - 1\}\}
直接暴力查询即可做到 O(qn)\mathcal{O}(qn)。
考虑将答案贡献分为三类：
  • max⁡prei≥l{i−prei}\displaystyle \max_{pre_i \geq l} \{i - pre_i\}。
  • max⁡prei<l{i−l}\displaystyle \max_{pre_i < l} \{i - l\}。
  • max⁡nxti>r{r−i}\displaystyle \max_{nxt_i > r} \{r - i\}。
将询问离线下来，分别做三次二维偏序即可。时间复杂度 O((n+q)log⁡n)\mathcal{O}((n + q)\log n)。
注意本题卡常，实现时注意以下细节：
  • 第二类的 prei<lpre_i < l 是可以直接将第一类按 prei≥lpre_i \geq l 排好序的数组倒着做的，不用再次排序。
  • 线段树不要在节点存储 l 和 r，而是在查询时记录。线段树清空时不要重新 build，直接 memset 扫过去即可。
Code：
CPP
#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a));

using namespace std;

const int maxn = 2e6 + 10, maxq = 2e6 + 10, maxa = 2e6 + 10;

struct Query{
    int l, r, idx;
} query[maxq];

namespace tree1{
    int tree[maxn << 2];
    inline void modify(int index, int L, int R, int x, int k){
        if (L == R){
            tree[index] = k;
            return;
        }
        const int mid = L + R >> 1;
        if (x <= mid){
            modify(index << 1, L, mid, x, k);
        }else{
            modify(index << 1 | 1, mid + 1, R, x, k);
        }
        tree[index] = max(tree[index << 1], tree[index << 1 | 1]);
    }

    inline int query(int index, int L, int R, int l, int r){
        if (L >= l && R <= r){
            return tree[index];
        }
        const int mid = L + R >> 1;
        int res = 0;
        if (l <= mid){
            res = max(res, query(index << 1, L, mid, l, r));
        }
        if (r > mid){
            res = max(res, query(index << 1 | 1, mid + 1, R, l, r));
        }
        return res;
    }
}

namespace tree2{
    int tree[maxn << 2];
    inline void modify(int index, int L, int R, int x, int k){
        if (L == R){
            tree[index] = k;
            return;
        }
        const int mid = L + R >> 1;
        if (x <= mid){
            modify(index << 1, L, mid, x, k);
        }else{
            modify(index << 1 | 1, mid + 1, R, x, k);
        }
        tree[index] = min(tree[index << 1], tree[index << 1 | 1]);
    }

    inline int query(int index, int L, int R, int l, int r){
        if (L >= l && R <= r){
            return tree[index];
        }
        const int mid = L + R >> 1;
        int res = 1e9;
        if (l <= mid){
            res = min(res, query(index << 1, L, mid, l, r));
        }
        if (r > mid){
            res = min(res, query(index << 1 | 1, mid + 1, R, l, r));
        }
        return res;
    }
}

int n, q;
int a[maxn], pos[maxa], pre[maxn], nex[maxn], id[maxn], res[maxq];

int main(){
    // freopen("B.in", "r", stdin);
    // freopen("B.out", "w", stdout);
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++){
        pre[i] = pos[a[i]], pos[a[i]] = i;
    }
    for (int i = 1; i <= n; i++){
        pos[a[i]] = n + 1;
    }
    for (int i = n; i; i--){
        nex[i] = pos[a[i]], pos[a[i]] = i;
    }
    iota(id + 1, id + n + 1, 1);
    for (int i = 1; i <= q; i++){
        scanf("%d %d", &query[i].l, &query[i].r), query[i].idx = i;
    }
    sort(id + 1, id + n + 1, [](int x, int y){return pre[x] < pre[y];});
    sort(query + 1, query + q + 1, [](Query x, Query y){return x.l < y.l;});
    for (int i = 1, p = 1; i <= q; i++){
        while (p <= n && pre[id[p]] < query[i].l){
            tree1::modify(1, 1, n, id[p], id[p]), p++;
        }
        res[query[i].idx] = max(res[query[i].idx], tree1::query(1, 1, n, query[i].l, query[i].r) - query[i].l);
    }
    mem(tree1::tree, 0);
    for (int i = q, p = n; i; i--){
        while (p && pre[id[p]] >= query[i].l){
            tree1::modify(1, 1, n, id[p], id[p] - pre[id[p]] - 1), p--;
        }
        res[query[i].idx] = max(res[query[i].idx], tree1::query(1, 1, n, query[i].l, query[i].r));
    }
    sort(id + 1, id + n + 1, [](int x, int y){return nex[x] > nex[y];});
    sort(query + 1, query + q + 1, [](Query x, Query y){return x.r > y.r;});
    mem(tree2::tree, 0x3f);
    for (int i = 1, p = 1; i <= q; i++){
        while (p <= n && nex[id[p]] > query[i].r){
            tree2::modify(1, 1, n, id[p], id[p]), p++;
        }
        res[query[i].idx] = max(res[query[i].idx], query[i].r - tree2::query(1, 1, n, query[i].l, query[i].r));
    }
    for (int i = 1; i <= q; i++){
        printf("%d\n", res[i]);
    }

return 0;
}

评论

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

正在加载评论...