早上刷NOIP的题刷到有点烦就想学点新东西，然后.....一个早上就这样过去了QAQ。虽然主席树不是NOIP考点，但是...或许我能活到省选呢？（美好的幻想）
题目的大意就是给定一个长度为n的区间，给出m个询问，每次询问一个区间[l,r]中第k小的树。
主席树（一种可持久化线段树）的入门题。
推荐一发学习资料：戳这里
感觉人家讲得很仔细了我也没什么讲的必要了......
总算是学了一种可持久化树了，好像也没想象中那么难？这道题的重点在query函数方面，建议自己在纸上模拟一下建树和查询操作，这样比较好理解一点。
感觉好妙啊~听说会了这个就不用学归并树啦~(≧▽≦)/~
代码：
#include<cstdio> #include<cstring> #include<algorithm> const int N=1e5+5; using namespace std; struct point{ int rt,sum,ls,rs; }e[N*20]; int a[N],b[N],tot=0,n,m,sz; void build(int &rt,int le,int ri) { tot++;rt=tot; e[rt].sum=0; if(le==ri)return ; int mid=(le+ri)>>1; build(e[rt].ls,le,mid); build(e[rt].rs,mid+1,ri); } void up(int &rt,int l,int r,int last,int p) { rt=++tot; e[rt].ls=e[last].ls;e[rt].rs=e[last].rs; e[rt].sum=e[last].sum+1; if(l==r)return; int mid=(l+r)>>1; if(p<=mid)up(e[rt].ls,l,mid,e[last].ls,p); else up(e[rt].rs,mid+1,r,e[last].rs,p); } int query(int ll,int rr,int l,int r,int k) { if(l==r)return l; int mid=(l+r)>>1; int c=e[e[rr].ls].sum-e[e[ll].ls].sum; if(k<=c)return query(e[ll].ls,e[rr].ls,l,mid,k); else return query(e[ll].rs,e[rr].rs,mid+1,r,k-c); } void find() { int ll,rr,kk; scanf("%d %d %d",&ll,&rr,&kk); int an=query(e[ll-1].rt,e[rr].rt,1,sz,kk); printf("%d ",b[an]); } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); sz=unique(b+1,b+n+1)-(b+1); build(e[0].rt,1,sz); for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+sz,a[i])-b; for(int i=1;i<=n;i++)up(e[i].rt,1,sz,e[i-1].rt,a[i]); while(m--)find(); return 0; }
然而......
接下来还是得滚回去学NOIP考点啊╭(╯^╰)╮ ，要是NOIP考挂就白学了QAQ。