题解：P9991 [Ynoi Easy Round 2023] TEST_107

Claire0918 · 2025-07-29 16:27:58 · 题解

要求值的类型比 [l, r] 少，考虑强制要求 [l, r] 中的一种值不能选。具体地，对于位置 i，设上一个与其相等的位置为 pre_i，下一个与其相等的位置为 nxt_i，那么答案即为

直接暴力查询即可做到 \mathcal{O}(qn)。

考虑将答案贡献分为三类：

将询问离线下来，分别做三次二维偏序即可。时间复杂度 \mathcal{O}((n + q)\log n)。

注意本题卡常，实现时注意以下细节：

• 第二类的 pre_i < l 是可以直接将第一类按 pre_i \geq l 排好序的数组倒着做的，不用再次排序。
• 线段树不要在节点存储 l 和 r，而是在查询时记录。线段树清空时不要重新 build，直接 memset 扫过去即可。

Code：

#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;
}