主席树

今天看了下主席树,感觉好神奇,代码精简而且实用,例如静态区间第k大之类的题,用主席树直接秒杀线段树套平衡树之类的写法。就是空间有点大。。
具体请参考:
1.clj的论文
2.博文一篇,代码写的很精炼:http://im.librazy.org/article/837/note-chairtree-via-functional-segtree/
其实很好理解的。
入门题:
hdu2665
静态区间第k小,注意题目描述可能不恰当。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define w(i) T[(i)].w
#define lson(i) T[(i)].l
#define rson(i) T[(i)].r
using namespace std;
const int maxn=1e5+10;
int n,m;
int a[maxn],p[maxn],b[maxn];
bool cmp(int i,int j)
{
    return a[i]<a[j];
}
typedef struct Node{
    int l,r,w;
    Node(){l=r=w=0;}
}Node;
Node T[maxn*20];
int root[maxn],sz;
void ins(int &i,int l,int r,int x)
{
    T[++sz]=T[i];i=sz;
    w(i)++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(x<=m) ins(lson(i),l,m,x);
    else ins(rson(i),m+1,r,x);
}
int query(int i,int j,int l,int r,int k)
{
    if(l==r) return l;
    int t=w(lson(j))-w(lson(i));
    int m=(l+r)>>1;
    if(t>=k) return query(lson(i),lson(j),l,m,k);
    else return query(rson(i),rson(j),m+1,r,k-t);
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++) {scanf("%d",&a[i]);p[i]=i;}
        sort(p+1,p+1+n,cmp);
        for(i=1;i<=n;i++) b[p[i]]=i;
        root[0]=0;sz=0;
        for(i=1;i<=n;i++)
        {
            root[i]=root[i-1];
            ins(root[i],1,n,b[i]);
        }
        int l,r,k;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&l,&r,&k);
            int tmp=query(root[l-1],root[r],1,n,k);
            printf("%d\n",a[p[tmp]]);
        }
    }
    return 0;
}