题意：带修改不带插入的区间k大。

裸的可持久化线段树。。由于有修改，要用树状数组维护。其它跟不带修改的可持久化线段树一样。

因为我没有找到网上用指针写的代码。。CLJ写这道题也用的不是可持久化线段树，于是我就没有任何模板可以参照。。就参考网上数组版的自己脑补了一个指针版。。你们就可以看到代码优美度下降了好多。

由于数字范围很大，我们需要把所有输入读进来然后离散化。。不离散化的话就要动态开点（这个我暂时还不会）

这份代码用的空间比较多。。在zju是A不了的，需要空间优化（怎么优化我也不知道）

1 #include
      
         2 #include
       
          3 const int MAXN=10000+5;  4 const int INF=~0U>>1;  5 const int BUFFER_SIZE=10000;  6 const int MAXM=10000+5;  7 struct Tree{  8     Tree* pl,*pr;  9     int l,r,sum; 10     Tree* set(int _l,int _r,Tree* _pl,Tree* _pr) 11     { 12         l=_l;r=_r;pl=_pl;pr=_pr; 13         sum=pl->sum+pr->sum; 14         return this; 15     } 16     Tree* set(int _l,int _r,int all); 17     Tree* add(int pos,int ad); 18 }; 19 Tree* buffer=0,*cur; 20 inline Tree* get() 21 { 22     if(!buffer || cur-buffer==BUFFER_SIZE) 23         buffer=new Tree[BUFFER_SIZE],cur=buffer; 24     return cur++; 25 } 26 Tree* Tree::set(int _l,int _r,int all) 27 { 28     l=_l;r=_r; 29     if(l+1==r) sum=all; 30     else 31     { 32         int m=(l+r)>>1; 33         pl=get()->set(l,m,all); 34         pr=get()->set(m,r,all); 35         sum=pl->sum+pr->sum; 36     } 37     return this; 38 } 39 Tree* Tree::add(int pos,int ad) 40 { 41     if(l+1==r) return get()->set(l,r,sum+ad); 42     int m=(l+r)>>1; 43     if(pos
        
         set(l,r,pl->add(pos,ad),pr); 44     else return get()->set(l,r,pl,pr->add(pos,ad)); 45 } 46 inline int lowbit(int x) 47 {    return x&-x;    } 48 int n,m; 49 Tree* root[MAXN]; 50 void update(int x,int pos,int ad) 51 { 52     for(;x<=n;x+=lowbit(x)) 53         root[x]=root[x]->add(pos,ad); 54 } 55 Tree* ptl[MAXN],*ptr[MAXN]; 56 int lnum,rnum; 57 inline void get_trees(int x,int y) 58 { 59     lnum=rnum=0; 60     for(;x>0;x-=lowbit(x)) 61         ptl[lnum++]=root[x]; 62     for(;y>0;y-=lowbit(y)) 63         ptr[rnum++]=root[y]; 64 } 65 inline int get_sum() 66 { 67     int cnt1=0,cnt2=0; 68     for(int i=0;i
         
          pl->sum; 69     for(int i=0;i
          
           pl->sum; 70     return cnt2-cnt1; 71 } 72 inline int query(int x,int y,int k) 73 { 74     get_trees(x-1,y); 75     while(ptr[0]->l +1 < ptr[0]->r) 76     { 77         int cnt=get_sum(); 78         if(cnt<=k) 79         { 80             k-=cnt; 81             for(int i=0;i
           
            pr; 82 for(int i=0;i
            
             pr; 83 } 84 else 85 { 86 for(int i=0;i
             
              pl; 87 for(int i=0;i
              
               pl; 88 } 89 } 90 return ptr[0]->l; 91 } 92 struct Ask{ 93 int kind,a,b,c; 94 }ask[MAXM]; 95 int w[MAXN],sortw[MAXN+MAXM]; 96 int main() 97 { 98 freopen("1.in","r",stdin); 99 scanf("%d%d",&n,&m);100 int p;101 for(int i=0;i
               
                set(0,nn,0);125 for(int i=1;i<=n;++i) root[i]=root[0]->add(w[i-1],1);126 for(int i=1;i<=n;++i) update(i+lowbit(i),w[i-1],1);127 for(int i=0;i