题目链接

动态找区间第k大 

在不知道主席树前想过啥。。。每给一个区间给每个区间排序。。。知道主席树后感觉好神奇。维护从小到大数的个数的前缀和，还有很多历史版本的树，通过差分来知道某个区间的前缀和。

主席树巧妙利用了之前建过的树，节约了空间

主席树

1.先建一最初的树（值空）

2.区间后移一格，加入一个结点，实际修改了logn个结点，不动的结点就赋值为之前建的结点

3.继续后移，重复2，把整个数组每个数建一颗树。这样有一个froot[] 存每个值对应的新建的树的根节点

板子抄的kuangbin 做了修改和注释，非递归建树，改为正着建树。

学习链接：https://blog.csdn.net/pengwill97/article/details/80920143

 

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 typedef long long ll; 6 int const maxn=1e5+10; 7 int m,n,q,a[maxn],b[maxn],tot,froot[maxn],c[maxn*40],lson[maxn*40],rson[maxn*40];//主席树的空间开n的40倍一般够了 8 void init_hash(int x[]){
   //数值离散 9     for(int i=1;i<=n;i++)b[i]=a[i];10     sort(b+1,b+n+1);11     m=unique(b+1,b+n+1)-b-1;12 }13 int get_hash(int x){14     return lower_bound(b+1,b+m+1,x)-b;15 }16 17 int update(int root,int pos,int val){
   //加入一个新的值后新的树，root是前一棵树18     int newroot=tot++,tmp=newroot;19     c[newroot]=c[root]+val;//新树的结点值=原先树的值+新加的20     int l=1,r=m;21     while(l
        
         >1;23         if(pos<=mid){
   //看修改的值位于哪颗子树上24             lson[newroot]=tot++;rson[newroot]=rson[root];//如果位于左子树上，则右子树的值可以利用原先的树25             newroot = lson[newroot];root=lson[root];26             r=mid;27         }28         else {29             rson[newroot]=tot++;lson[newroot]=lson[root];30             newroot=rson[newroot];root=rson[root];31             l=mid+1;32         }33         c[newroot]=c[root]+val;34     }35     return tmp;//新的树的根节点36 }37 int query(int lr,int rr,int k){38     int l=1,r=m,mid;39     while(l
         
          >1;        41         if(c[lson[rr]]-c[lson[lr]]>=k){
   //求l-r区间，用r树-(l-1)树 ，如果左子树有k个了，同时向左子树跳42             r=mid;43             lr=lson[lr],rr=lson[rr];44         }45         else{
   //右子树有j(
          
           >1;57 lson[root]=build(l,mid);58 rson[root]=build(mid+1,r);59 }60 return root;61 }62 inline int get_num(){ //此题有负数！absolute value63 char ch;64 bool flag=false;65 int num=0;66 ch=getchar();67 while(ch<'0'||ch>'9'){ if(ch=='-')flag=true;ch=getchar();}68 while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+ch-'0';ch=getchar();}69 if(flag)return -1*num;70 return num;71 }72 int main(){73 scanf("%d%d",&n,&q);74 tot=0;75 for(int i=1;i<=n;i++)a[i]=get_num();76 77 init_hash(a);78 froot[0]= build(1,m);79 for(int i=1;i<=n;i++){80 int pos=get_hash(a[i]);81 froot[i]=update(froot[i-1],pos,1);82 }83 while(q--){84 int l,r,k;85 l=get_num(),r=get_num(),k=get_num();86 printf("%d\n",b[query(froot[l-1],froot[r],k)]);87 }88 return 0;89 }