动态维护区间第K大（带单点修改）

  1 //BZOJ 1901  2 #include<cstdio>  3 #include<cstring>  4 #include<cstdlib>  5 #include<iostream>  6 #include<algorithm>  7 #define rep(i,n) for(int i=0;i<n;++i)  8 #define F(i,j,n) for(int i=j;i<=n;++i)  9 #define D(i,j,n) for(int i=j;i>=n;--i) 10 #define lowbit(x) ((x)&(-(x))) 11 using namespace std; 12 const int N=110086; 13  14 struct Tree{ 15     int cnt,l,r; 16 }t[N*30]; 17 int n,m,num=0,root[N],a[N>>1],b[N],dat[N>>1][4],size=0,cnt=0; 18 int lc,rc,ln[N],rn[N]; 19  20 #define mid (l+r>>1) 21 void build(int &o,int l,int r){ 22     o=++cnt; t[o].cnt=0; 23     if (l==r) return; 24     build(t[o].l,l,mid); 25     build(t[o].r,mid+1,r); 26 } 27  28 void updata(int &o,int l,int r,int pos,int val){ 29     t[++cnt]=t[o],o=cnt,t[o].cnt+=val; 30     if (l==r) return; 31     if (pos <= mid) updata(t[o].l,l,mid,pos,val); 32     else updata(t[o].r,mid+1,r,pos,val); 33 } 34  35 void modify(int x,int pos,int val){ 36     for(x;x<=n;x+=lowbit(x) )//一次改logn棵树 37         updata(root[x],1,num,pos,val); 38 } 39  40 int query(int i,int j,int rank){ 41     int l=1,r=num; 42     int tl=0,tr=0; 43      44     while(l!=r){ 45         tl=tr=0; 46         F(i,1,lc) tl+=t[t[ln[i]].l].cnt;//将logn棵树的和加出来 47         F(i,1,rc) tr+=t[t[rn[i]].l].cnt; 48         if (tr-tl>=rank){ 49             F(i,1,lc) ln[i]=t[ln[i]].l;//向左找 50             F(i,1,rc) rn[i]=t[rn[i]].l; 51             r=mid; 52         } 53         else{ 54             F(i,1,lc) ln[i]=t[ln[i]].r;//向右找 55             F(i,1,rc) rn[i]=t[rn[i]].r; 56             l=mid+1; rank-=tr-tl;  57         } 58          59     } 60     return l; 61 } 62 #undef mid 63 int getans(int l,int r,int k){ 64     rc=lc=0; 65     for(r;r;r-=lowbit(r)) 66         rn[++rc]=root[r]; 67     for(l;l;l-=lowbit(l)) 68         ln[++lc]=root[l]; 69     return query(1,num,k); 70 } 71  72 void solve(){ 73     sort(b+1,b+size+1); 74     num=unique(b+1,b+size+1)-b-1;//这个神奇的用法……是什么意思？ 75     F(i,1,n) a[i]=lower_bound(b+1,b+num+1,a[i])-b; 76     build(root[0],1,num); 77     F(i,1,n) modify(i,a[i],1); 78     F(i,1,m){ 79         if(dat[i][0]==0) printf("%d\n",b[ getans(dat[i][1]-1,dat[i][2],dat[i][3]) ]); 80         else{ 81             int pos=lower_bound(b+1,b+num+1,dat[i][2])-b; 82             modify(dat[i][1],a[dat[i][1]],-1); 83             a[dat[i][1]]=pos; 84             modify(dat[i][1],a[dat[i][1]],1); 85         } 86     } 87 } 88  89 int main(){ 90     #ifndef ONLINE_JUDGE 91     freopen("file.in","r",stdin); 92     #endif 93     int T=1; 94 //    scanf("%d",&T); 95     while(T--){ 96         size=cnt=num=0; 97         memset(b,0,sizeof b); 98         memset(t,0,sizeof t); 99         memset(dat,0,sizeof dat);100         scanf("%d%d",&n,&m);101         F(i,1,n){102             scanf("%d",&a[i]);103             b[++size]=a[i];104         }105         char cmd[3];106         F(i,1,m){107             scanf("%s",cmd);108             if (cmd[0]==‘C‘){109                 dat[i][0]=1;110                 scanf("%d%d",&dat[i][1],&dat[i][2]);111                 b[++size]=dat[i][2];112             }113             else{114                 dat[i][0]=0;115                 scanf("%d%d%d",&dat[i][1],&dat[i][2],&dat[i][3]);116             }117         }118         solve();119     }120     return 0;121 }122 /************************************************** 123 利用BIT的思想，实现前缀-差分的logn的转化124 裸的可持久化线段树是每棵树维护一个区间[1,i](前缀和) 125 查询O(1),而修改就需要 O(n)了126 而动态进行修改&查询-->BIT里套一个可持久化线段树127 BIT的每个节点表示原数组的一个区间128 然后用可持久化线段树来维护这个区间 129 查询的时候log(n)棵线段树一起查130 **************************************************/