MnZn第一次自己发帖，求别喷（（（

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500005;
const ll inf = 1e10;

struct segnode{
    int pl = 0;
    int lc = 0, rc = 0;
    void operator=(const segnode b){
        pl = b.pl;
        lc = b.lc;
        rc = b.rc;
    }
};

struct chairmantree{
    ll nodecnt, rt[maxn << 2];
    segnode tr[maxn << 2];
    segnode tag[maxn << 2];
    inline void pushup(int x, int k){tr[x].pl = tr[k].pl + 1;}
    inline int build(int l, int r, int a[]){
        int p = ++nodecnt;
        if(l == r){
            tr[p].pl = 0;
            return p;
        }
        int mid = (l + r) >> 1;
        tr[p].lc = build(l, mid, a);
        tr[p].rc = build(mid + 1, r, a);
        return p;
    }
    inline int insert(int cur, int l, int r, int pos, int k){
        int p = ++nodecnt;
        tr[p] = tr[cur];
        pushup(p, cur);
        if(l > r) return p;
        if(l == r){
            // tr[p].pl = k;
            return p;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) tr[p].lc = insert(tr[cur].lc, l, mid, pos, k);
        else tr[p].rc = insert(tr[cur].rc, mid + 1, r, pos, k);
        return p;
    }
    inline int querykth(int p, int q, int l, int r, int k){
        // segnode ans = {0};
        if(l == r){
            return l;
        }
        int mid = (l + r) >> 1;
        int lans = tr[tr[p].lc].pl - tr[tr[q].lc].pl;
        if(k <= lans){
            return querykth(tr[p].lc, tr[q].lc, l, mid, k);
        }
        else{
            return querykth(tr[p].rc, tr[q].rc, mid + 1, r, k - lans);
        }
    }
}tree;

int n, m;
int lst[maxn], val[maxn], num[maxn], dis[maxn];
int discre(int *lst, int *val, int *dis){
	sort(val + 1, val + n + 1);
	int len = unique(val + 1, val + 1 + n) - val - 1;
	for(int i = 1;i <= n;i++){
		dis[i] = lower_bound(val + 1, val + len + 1, lst[i]) - val;
        num[dis[i]] = dis[i];
	}
    return len;
}

int main(){
    // freopen("P3834.out", "w", stdout);
    cin >> n >> m;
    // tree.tr[0].pl = -1;
    for(int i = 1;i <= n;i++){
        cin >> lst[i];
        val[i] = lst[i];
    }
    int l = discre(lst, val, dis);
    tree.rt[0] = tree.build(1, l, num);
    for(int i = 1;i <= n;i++){
        int a = dis[i];
        tree.rt[i] = tree.insert(tree.rt[i-1], 1, l, a, 1);
    }
    while(m --){
        int op, x, y;
        cin >> x >> y >> op;
        cout << val[tree.querykth(tree.rt[y], tree.rt[x-1], 1, l, op)] << endl;
    }
} 
// 模板是从书上抄来的

记录

蒟蒻刚学主席树，洛谷上过了，本地从第三个点开始WAqwq, 一直输出最大值，求各位dalao看看有什么地方不对qwq