主席树：POJ2104 K-th Number (主席树模板题)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 struct Node{
 6     int a,b,rs,ls,sum;
 7 }tr[2000010];
 8 int a[100010],b[100010];
 9 int rt[100010],pos,cnt;
10 void Build(int &node,int a,int b)
11 {
12     node=++cnt;
13     tr[node].a=a;
14     tr[node].b=b;
15     if(a==b)return;
16     int mid=(a+b)>>1;
17     Build(tr[node].ls,a,mid);
18     Build(tr[node].rs,mid+1,b);
19 }
20 
21 void Insert(int pre,int &node)
22 {
23     node=++cnt;
24     tr[node].ls=tr[pre].ls;
25     tr[node].rs=tr[pre].rs;
26     tr[node].a=tr[pre].a;
27     tr[node].b=tr[pre].b;
28     tr[node].sum=tr[pre].sum+1;
29     if(tr[node].a==tr[node].b)return;
30     int mid=(tr[node].a+tr[node].b)>>1;
31     if(mid>=pos)Insert(tr[pre].ls,tr[node].ls);
32     else Insert(tr[pre].rs,tr[node].rs);
33 }
34 int Query(int pre,int node,int k)
35 {
36     if(tr[node].ls==tr[node].rs)return b[tr[node].a];
37     int cmp=tr[tr[node].ls].sum-tr[tr[pre].ls].sum;
38     if(cmp>=k)return Query(tr[pre].ls,tr[node].ls,k);
39     else return Query(tr[pre].rs,tr[node].rs,k-cmp);
40 }
41 int main()
42 {
43     int n,q;
44     scanf("%d%d",&n,&q);
45     for(int i=1;i<=n;b[i]=a[i],i++)
46         scanf("%d",&a[i]);
47     sort(b+1,b+n+1);
48     Build(rt[0],1,n);
49     for(int i=1;i<=n;i++)
50     {
51         pos=lower_bound(b+1,b+n+1,a[i])-b;
52         Insert(rt[i-1],rt[i]);
53     }    
54     int l,r,k;
55     for(int i=1;i<=q;i++)
56     {
57         scanf("%d%d%d",&l,&r,&k);
58         printf("%d\n",Query(rt[l-1],rt[r],k));
59     }
60     return 0;
61 }