POJ 2104 K-th Number（主席树模板题）

题意：
求区间$[l,r]$的第k小。

思路：
主席树不好理解啊，简单叙述一下吧。

主席树就是由多棵线段树组成的，对于数组$a[1,2...n]$，对于每个i，我们都去建立一棵线段树维护$a[1,..i]$出现的数的个数。

但是如果每一棵线段树都去新建结点的话，那这内存的开销是十分巨大的。。。

我们可以发现，第i棵线段树和第i-1棵线段树有很多结点都是相同的，这样一来，我们就没必要再去重新新建结点了，直接套用上一棵线段树的结点即可。

这里我想引用一张某大神博客的手绘图解：（来自http://blog.csdn.net/regina8023/article/details/41910615）

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 #include<set>
 11 using namespace std;
 12 typedef long long ll;
 13 const int INF = 0x3f3f3f3f;
 14 const int maxn=100000+5;
 15 
 16 int n, m;
 17 int tot_num;
 18 int tot=0;
 19 int b[maxn],c[maxn],t[maxn];
 20 
 21 struct node
 22 {
 23     int l,r,num;
 24 }a[maxn*50];
 25 
 26 int build(int l ,int r)
 27 {
 28     int root=++tot;
 29     a[root].num=0;
 30     if(l==r)  return root;
 31     int mid=(l+r)>>1;
 32     a[root].l=build(l,mid);
 33     a[root].r=build(mid+1,r);
 34     return root;
 35 }
 36 
 37 int update(int root, int x)
 38 {
 39     int now=++tot;
 40     int tmp=now;
 41     a[tot].num=a[root].num+1;
 42     int l=1,r=tot_num;
 43     while(l<r)
 44     {
 45         int mid=(l+r)>>1;
 46         if(x<=mid)
 47         {
 48             a[now].l=++tot;
 49             a[now].r=a[root].r;  //这儿不需修改，套用上一棵线段树的数即可
 50             root=a[root].l;
 51             now=tot;
 52             r=mid;
 53         }
 54         else
 55         {
 56             a[now].l=a[root].l;  //同理
 57             a[now].r=++tot;
 58             root=a[root].r;
 59             now=tot;
 60             l=mid+1;
 61         }
 62         a[now].num=a[root].num+1;
 63     }
 64     return tmp;
 65 }
 66 
 67 int query(int ql, int qr, int k)
 68 {
 69     int l=1,r=tot_num;
 70     while (l<r)
 71     {
 72         int mid=(l+r)>>1;
 73         if (a[a[qr].l].num-a[a[ql].l].num>=k)  //>=k，说明肯定在该区间内，继续往下缩小范围
 74         {
 75             r=mid;
 76             ql=a[ql].l;
 77             qr=a[qr].l;
 78         }
 79         else
 80         {
 81             l=mid+1;
 82             k-=a[a[qr].l].num-a[a[ql].l].num; //<k，说明左区间的数不够，先减去左区间的数，然后往右区间搜索
 83             ql=a[ql].r;
 84             qr=a[qr].r;
 85         }
 86     }
 87     return l;
 88 }
 89 
 90 int main()
 91 {
 92    //freopen("in.txt","r",stdin);
 93    scanf("%d%d",&n,&m);
 94    for(int i=1;i<=n;i++)
 95    {
 96        scanf("%d",&c[i]);
 97        b[i]=c[i];
 98    }
 99    sort(b+1,b+n+1);
100    tot_num=unique(b+1,b+n+1)-b-1;
101    t[0]=build(1,tot_num);  //初始化
102    for(int i=1;i<=n;i++)
103    {
104        t[i]=update(t[i-1],lower_bound(b+1,b+tot_num+1,c[i])-b);
105    }
106    while(m--)
107    {
108        int l,r,k;
109        scanf("%d%d%d",&l,&r,&k);
110        printf("%d
",b[query(t[l-1],t[r],k)]);
111    }
112    return 0;
113 }