1、题目大意:区间第k小,什么修改没有。。。
2、分析:这个是可持久化线段树,也是主席树,解释一下,n个线段树是怎么存下的,就是每一颗线段树和前一个有logn个点不一样
然后我们只需要一个线段树开logn的空间,然后其他的指针指向上一个线段树对应的地方也是可以的对吧
然后。。然后就没了。。
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int a[2000010], l[2000010]; pair<int , int> b[2000010]; int T[2000010], ls[2000010], rs[2000010]; int h[2000010]; int cnt[2000010]; int tot; int num = 0; inline int insert(int root, int pos){ int nroot = ++ tot; int ret = nroot; int l = 1, r = num; cnt[nroot] = cnt[root] + 1; while(l < r){ int mid = (l + r) / 2; if(pos <= mid){ r = mid; ls[nroot] = ++ tot; rs[nroot] = rs[root]; nroot = ls[nroot]; root = ls[root]; cnt[nroot] = cnt[root] + 1; } else { l = mid + 1; ls[nroot] = ls[root]; rs[nroot] = ++ tot; nroot = rs[nroot]; root = rs[root]; } cnt[nroot] = cnt[root] + 1; } return ret; } inline int query(int lll, int rrr, int k){ int l = 1, r = num; int le_ = T[lll - 1]; int ri_ = T[rrr]; while(l < r){ int mid = (l + r) / 2; int q = cnt[ls[ri_]] - cnt[ls[le_]]; if(k <= q){ r = mid; le_ = ls[le_]; ri_ = ls[ri_]; } else{ l = mid + 1; k -= q; le_ = rs[le_]; ri_ = rs[ri_]; } } return l; } int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++){ scanf("%d", &a[i]); b[i] = make_pair(a[i], i); } sort(b + 1, b + n + 1); b[0].first = -2147483647; for(int i = 1; i <= n; i ++){ if(b[i].first != b[i - 1].first) num ++; l[b[i].second] = num; h[num] = b[i].second; } T[0] = 1; tot = 1; for(int i = 1; i <= n; i ++) T[i] = insert(T[i - 1], l[i]); for(int i = 1; i <= m; i ++){ int l, r, k; scanf("%d%d%d", &l, &r, &k); printf("%d\n", a[h[query(l, r, k)]]); } return 0; }