【洛谷 P3834】可持久化线段树1（主席树）

主席树=可持久化权值线段树。

如果你不会可持久化线段树，请右转

如果你不会权值线段树，请自行脑补，就是线段树维护值域里有多少个数出现。

可持久化线段树是支持查询历史版本的。

我们对每个数都进行一次基于上个版本的单点修改操作，这样每个版本就是维护的前\(p\)个数，这个权值显然满足可减性。

所以，要查询区间\([l,r]\)的第\(k\)大时，我们就用第\(r\)个版本减去第\(l-1\)个版本，我们就得到了一颗\([l,r]\)的权值线段树，然后跑第\(k\)小就简单了：

如果左儿子有大于等于\(k\)个数，就继续去左儿子找第\(k\)小，否则设左儿子的值为\(lcnt\)，去右儿子找第\(k-lcnt\)小。

#include <cstdio>

#include <algorithm>

using std::sort;

#define re register

inline int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }

	while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }

	return s * w;

}

const int MAXN = 200010;

const int MAXM = 200010;

const int MAXMLOGN = 4000010;

struct SegTree{

    int lc, rc, cnt;

    SegTree(){ lc = rc = cnt = 0; }

}t[MAXMLOGN];

int root[MAXM];

int a[MAXN], c[MAXN], d[MAXN];

int n, m, tot, num;

int build(int l, int r){

    int id = ++tot;

    if(l == r) return id;

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

    t[id].lc = build(l, mid);

    t[id].rc = build(mid + 1, r);

    return id;

}

int insert(int now, int l, int r, int x){

    int id = ++tot;

    t[id] = t[now];

    if(l == r){ ++t[id].cnt; return id; }

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

    if(x <= mid) t[id].lc = insert(t[now].lc, l, mid, x);

    else t[id].rc = insert(t[now].rc, mid + 1, r, x);

    t[id].cnt = t[t[id].lc].cnt + t[t[id].rc].cnt;

    return id;

}

int ask(int p, int q, int l, int r, int k){

    if(l == r) return l;

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

    int L = t[t[p].lc].cnt - t[t[q].lc].cnt;

    if(k <= L) return ask(t[p].lc, t[q].lc, l, mid, k);

    else return ask(t[p].rc, t[q].rc, mid + 1, r, k - L);

}

struct divide{

    int id, val;

    bool operator < (const divide A) const{

        return val < A.val;

    }

}b[MAXN];

int l, r, k;

int main(){

    n = read(); m = read();

    for(re int i = 1; i <= n; ++i){

       b[i].val = a[i] = read();

       b[i].id = i;

    }

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

    b[0].val = -2147483646;

    for(int i = 1; i <= n; ++i)

       if(b[i].val != b[i - 1].val){

         c[b[i].id] = ++num;

         d[num] = b[i].val;

       }

       else c[b[i].id] = num;

    root[0] = build(1, num);

    for(int i = 1; i <= n; ++i)

       root[i] = insert(root[i - 1], 1, num, c[i]);

    for(re int i = 1; i <= m; ++i){

       l = read(); r = read(); k = read();

       printf("%d\n", d[ask(root[r], root[l - 1], 1, num, k)]);

    }

    getchar();

    return 0;

}

巴特西

【洛谷 P3834】可持久化线段树1（主席树）

最新文章

热门文章

巴特西

【洛谷 P3834】 可持久化线段树1（主席树）

最新文章

热门文章

【洛谷 P3834】可持久化线段树1（主席树）