POJ-2104 区间第k大-主席树板子

原题地址
主席树是可持久化的线段树，每加入一个节点都建一棵线段树，但是不需要建立一棵完整的树，因为更新一个点只会影响log（n）个节点。不变的节点建立一个联系就可以。先来个经典题存个板子。以后再来填坑。。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1e5+5;
int a[N], cnt, root[N], n, m, x, y, k;
struct node{int l, r, sum; }T[N*50];
vector<int>v;
int getid(int x) {return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;}
void update(int l,int r, int &x, int y, int pos) {
  T[++cnt] = T[y], T[cnt].sum++; x = cnt;
  if(l == r) return;
  int mid = (l + r) / 2;
  if(mid >= pos) update(l, mid, T[x].l, T[y].l, pos);
  else update(mid+1, r , T[x].r, T[y].r, pos);
}
int query(int l, int r, int x, int y, int k) {
  if(l == r) return l;
  int mid = (l + r) / 2;
  int sum = T[T[y].l].sum - T[T[x].l].sum;
  if(sum >= k)return query(l, mid, T[x].l, T[y].l, k);
  else return query(mid+1, r, T[x].r, T[y].r, k - sum);
}
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    v.push_back(a[i]);
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for(int i = 1; i <= n; i++) update(1, n , root[i], root[i-1], getid(a[i]));
  for(int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &k);
    printf("%d\n", v[query(1, n, root[x-1], root[y], k) - 1]);
  }
}