可持久化线段树

saxiy · 2019-10-30 18:17:17 · 个人记录

以前写的主席树

#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include <bits/stdc++.h>
#define RS register
#define N 200005
using namespace std;

int n, sn, m, a[N], inv[N], root[N];
int sum[N << 4], ch[N << 4][2], cnt = 1;

void build() { root[0] = ch[1][0] = ch[1][1] = 1; }

void add(int pt, int &nt, int l, int r, int k) {
    RS int now = (nt = ++cnt), mid, c;
    while(l != r) {
        sum[now] = sum[pt] + 1;
        mid = l + r >> 1;
        if(k > mid) l = mid + 1, c = 1;
        else r = mid, c = 0;
        ch[now][c ^ 1] = ch[pt][c ^ 1];
        now = ch[now][c] = ++cnt;
        pt = ch[pt][c];
    } sum[now] = sum[pt] + 1;
}

int query(int pt, int nt, int l, int r, int k) {
    RS int s, mid, c;
    while(l != r) {
        s = sum[*ch[nt]] - sum[*ch[pt]];
        mid = l + r >> 1;
        if(k > s) k -= s,
            l = mid + 1, c = 1;
        else r = mid, c = 0;
        pt = ch[pt][c]; nt = ch[nt][c];
    }
    return l;
}

inline int read() {
    RS int x = 0; RS char c(getchar()); bool f = 1;
    for(;!isdigit(c);c = getchar()) if(c == '-') f = 0;
    for(; isdigit(c);c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    return f ? x : -x;
}

int main() {
    n = read(); m = read();
    for(int i = 1;i <= n;i++)
        a[i] = inv[i] = read();
    sort(a + 1, a + n + 1);
    sn = unique(a + 1, a + n + 1) - a - 1;
    build();
    for(int i = 1;i <= n;i++) {
        inv[i] = lower_bound(a + 1, a + sn + 1, inv[i]) - a;
        add(root[i - 1], root[i], 1, sn, inv[i]);
    }
    RS int l, r, k;
    while(m--) {
        l = read(); r = read(); k = read();
        printf("%d\n", a[query(root[l - 1], root[r], 1, sn, k)]);
    }
    return 0;
}