题目大意：查询区间k大值
关于主席树：
主席树（可持久化线段树，函数式线段树）
解决区间k大值 用到前缀和思想
如果前L-1的3个最大值1 2 3 前R个的3个最大值是4 5 6那么前三大就是4 5 6那如果前R个数前三大是1 5 6呢？那就必须要知道没个数的个数了！因为后面的数2与前面的数做差不就可以了吗？但题目是k个数啊 那就维护k个数呗！ 线段树！建立n+1棵线段树，统计每个数到sz[i]时出现的次数，线段树R比线段树L-1多出来的数中第k大就是答案！但超空间啊把所有数排序，去重，线段树中存储的不是数本身而是数的排序 还是空间......解决方法：公用节点。建立过程：
1.排序，去重sz 2 4 6 8 8 6 4 2
hash 2 4 6 8改成序号 1 2 3 4 4 3 2 12.建立线段树先建立空线段树（要用到前缀和）然后再根据每一个hash值建立线段树，每加一个数就增加一条链
实现跟线段树差不多
//主席树模板 #include#include #include #include using namespace std;const int maxn=100005;const int maxnn=10000000;int root[maxn],ls[maxnn],rs[maxnn],cnt[maxnn],tot;int sz[maxn],hash[maxn];void build(int &cur,int l,int r)//建立一棵空树 { cur=tot++; cnt[cur]=0; if(l!=r) { int mid=(l+r)/2; build(ls[cur],l,mid); build(rs[cur],mid+1,r); }}void updata(int pre,int ps,int &cur,int l,int r)//往上加线段树 { cur=tot++; cnt[cur]=cnt[pre]+1; ls[cur]=ls[pre];rs[cur]=rs[pre]; if(l==r)return; int mid=(l+r)/2; if(ps<=mid)updata(ls[pre],ps,ls[cur],l,mid); else updata(rs[pre],ps,rs[cur],mid+1,r);}int query(int lt,int rt,int l,int r,int k)//查询k大值 { if(l==r) return l; int mid=(l+r)/2,differ=cnt[ls[rt]]-cnt[ls[lt]]; if(k<=differ)return query(ls[lt],ls[rt],l,mid,k); else return query(rs[lt],rs[rt],mid+1,r,k-differ); }int main(){ int n,m,l,r,k; while(scanf("%d%d",&n,&m)==2) { for(int i=1;i<=n;i++) { scanf("%d",sz+i); hash[i]=sz[i]; } sort(hash+1,hash+n+1); int size=unique(hash+1,hash+n+1)-hash-1;//数组去重 for(int i=1;i<=n;i++) sz[i]=lower_bound(hash+1,hash+size+1,sz[i])-hash;//得到序号 tot=0; build(root[0],1,size); for(int i=1;i<=n;++i) updata(root[i-1],sz[i],root[i],1,size); while(m--) { scanf("%d%d%d",&l,&r,&k); printf("%d\n",hash[query(root[l-1],root[r],1,size,k)]); } } return 0;}
//hja 大神的代码 指针版 #include#include #include #include #define nd(x) (nil + (x))using namespace std;const int lim = 1e9; const int N = 100010; const int lg = 60; struct node { int s; node *lc, *rc; };node nil[N * lg], *rot[N]; int cnt; int n, m, a[N], dc[N]; node* insert(node *u, int l, int r, int p) { node *ret = nd(++cnt); *ret = *u, ret->s ++; if(l == r) return ret; int mid = (l + r) / 2; if(p <= mid) ret->lc = insert(ret -> lc, l, mid, p); else ret->rc = insert(ret -> rc, mid + 1, r, p); return ret;}int query(node *u, node *v, int l, int r, int k) { if(l == r) return dc[l]; int mid = (l + r) / 2; int c = u -> lc -> s - v -> lc -> s; if(k <= c) return query(u -> lc, v -> lc, l, mid, k); return query(u -> rc, v -> rc, mid + 1, r, k - c); }void read() { cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i]; }void prep() { for(int i=1; i<=n; i++) dc[i] = a[i]; sort(dc+1, dc+n+1), dc[0] = unique(dc+1, dc+n+1) - dc - 1; for(int i=1; i<=n; i++) a[i] = lower_bound(dc+1, dc+dc[0]+1, a[i]) - dc;}void solve() { cnt = nil->s = 0, rot[0] = nil->lc = nil->rc = nil; for(int i = 1; i <= n; i++) rot[i] = insert(rot[i-1], 1, dc[0], a[i]); while(m--) { int l, r, k; cin >> l >> r >> k; cout << query(rot[r], rot[l - 1], 1, dc[0], k) << endl; }}int main() { read(); prep(); solve(); return 0; }