学习了一下主席树，感觉具体算法思路不大好讲。。
大概是先建个空线段树，然后类似于递推，每一个都在前一个“历史版本”的基础上建立一个新的“历史版本”，每个历史版本只需占用树高个空间（好神奇！）
查询时这道题是通过“历史版本”间作差解决
*另外提一下，在建立“历史版本”的过程中，是“新建”，而不是“更新”，是先copy过来原有的，再按个人需求改成自己的，所产生的一个新的“历史版本”
希望注释能有帮助
//吐槽一下，本人看kuangbin模板看得好费劲，一方面不习惯用lson[],rson[]数组搞线段树，另一方面他的update query函数都是用二分写的，看半天没理解。。。
以下是按个人习惯加了注释的代码
#include#include #include #include #include #include #include #define M 100000+5 using namespace std; const int N=1e5+7;const int INF=0x3f3f3f3f;struct node{ int l,r; //l,r分别指向左右孩子，但由于历史的错乱，二者的值未必有规律 int size; //当前历史版本里，该节点中所包含的元素个数 //p.s. 在最后一个历史版本里，size即为总元素个数n }tr[N*20];//主席树的初始状态为一“空架子”//每次updata都在前一“历史版本”基础上新建h个结点，共updata n次，产生了n个历史版本，每个版本占用空间为h*sizeof(one node) int tot; //结点建立顺序|所赋标号 int n; //共n个数 int a[N]; //读入数组int root[N];//记录a[]中每一个数对应各“历史版本”在主席树中的根结点标号 int m; //t[]中元素个数 int t[N]; //离散数组int pos(int x){ return lower_bound(t+1,t+1+m,x)-t;}int q; //q个询问int build(int l,int r){ int rt=tot++; tr[rt].size=0; if(l==r) return rt; int mid=(l+r)>>1; tr[rt].l=build(l,mid); tr[rt].r=build(mid+1,r); return rt;}// pre_node：最近一历史，[l,r]当前所更新到的包含x的区间 // x此次更新的“终点”// 沿途要增加的“权值”// p.s. 1<=l<=r<=m int updata(int pre_node,int l,int r,int x,int v){ int rt=tot++; //rt为新结点的标号 tr[rt]=tr[pre_node]; //先拷贝原指向当前区间的结点 tr[rt].size+=v; // 在函数不断向下深入过程中，更新node.size if(l==r) return rt; int mid=(l+r)>>1; if(x<=mid) tr[rt].l=updata(tr[pre_node].l,l,mid,x,v); else tr[rt].r=updata(tr[pre_node].r,mid+1,r,x,v); return rt; // 在函数逐步return过程中，更新node.l|r }// ql,qr反应的是在a[]中的下标，对应着更新到该下标时的“历史版本” // l，r反应的是在t[]中的下标 int query(int ql,int qr,int l,int r,int k){ if(l==r) return l; int diff=tr[tr[qr].l].size-tr[tr[ql].l].size;//在更新到ql位置和更新到qr位置时两个“历史版本”下左孩子的size之差 // p.s. size的大小反应较小数的多少 int mid=(l+r)>>1; if(diff>=k) return query(tr[ql].l,tr[qr].l,l,mid,k); else return query(tr[ql].r,tr[qr].r,mid+1,r,k-diff);}int main(){ while(~scanf("%d%d",&n,&q)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[i]=a[i]; sort(t+1,t+1+n); m=unique(t+1,t+1+n)-t-1; m++,t[m]=INF; tot=0; root[0]=build(1,m); //初始化一个空线段树 for(int i=1;i<=n;i++) { int order=pos(a[i]); root[i]=updata(root[i-1],1,m,order,1); //每次在上一次已完成的基础上新增h个结点 //从根 逐步新建结点到 a[i]在线段树上所对应的位置 //在这个逐步新建结点的过程中，要新建的结点的l，r始终满足l<=m<=r //这些结点每一个的size都在pre_node的基础上+1 } while(q--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",t[query(root[l-1],root[r],1,m,k)]); } }}