P4137 Rmq Problem / mex（主席树）

传送门

思路：

直接上主席树，对于每个询问\((l,r)\)，我们在第\(r\)个版本的主席树中查询最晚出现的小于\(l\)最小的数就行了。

因为答案可能为\(a_i+1\)，所以我们在离散化的时候考虑将\(a_i+1\)加进去。

一开始主席树部分没有思考清楚，还是对主席树的理解不够深入吧。。。其实就是一个维护前缀信息的数，后面的信息如果和前面有重复的，在这题中会直接将原来的覆盖掉。反正按照前缀树来思考就行啦~

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 200005;

int n, m;

int a[N], b[N << 1];

int D;

void Hash() {

    sort(b + 1, b + D + 1);

    D = unique(b + 1, b + D + 1) - b - 1;

    for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + D + 1, a[i]) - b;

}

int rt[N * 22], ls[N * 22], rs[N * 22], minv[N * 22], tot;

void build(int &o, int l, int r) {

    o = ++tot; minv[o] = 0;

    if(l == r) return;

    int mid = (l + r) >> 1;

    build(ls[o], l, mid); build(rs[o], mid + 1, r);

}

void insert(int &o, int last, int l, int r, int p, int v) {

    o = ++tot;

    ls[o] = ls[last]; rs[o] = rs[last];

    if(l == r) {

        minv[o] = v; return;

    }

    int mid = (l + r) >> 1;

    if(p <= mid) insert(ls[o], ls[last], l, mid, p, v);

    else insert(rs[o], rs[last], mid + 1, r, p, v);

    minv[o] = min(minv[ls[o]], minv[rs[o]]);

}

int query(int o, int l, int r, int lim) {

    if(l == r) return l;

    int mid = (l + r) >> 1;

    if(minv[ls[o]] <= lim) return query(ls[o], l, mid, lim);

    return query(rs[o], mid + 1, r, lim);

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> a[i], b[++D] = a[i], b[++D] = a[i] + 1;

    b[++D] = 0;

    Hash();

    build(rt[0], 1, D);

    for(int i = 1; i <= n; i++) insert(rt[i], rt[i - 1], 1, D, a[i], i);

    while(m--) {

        int l, r; cin >> l >> r;

        cout << b[query(rt[r], 1, D, l - 1)] << '\n';

    }

    return 0;

}

巴特西

P4137 Rmq Problem / mex（主席树）

最新文章

热门文章