P2617 Dynamic Ranking（树状数组套主席树模板）
hhz6830975
2017-12-25 19:22:56
我是看这个学会的：https://www.cnblogs.com/Empress/p/4659824.html
树状数组套主席树可以实现带修改的主席树
树状数组每个元素内含一颗权值线段树，初始化逐个动态加点，修改同理，空间复杂度 O(nlognlogn)
~~然而我并不知道这和主席树有什么关系~~
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10010;
int n,m,a[maxn];
int hash[maxn*2],hashN;
inline int read(){
int ret=0,sign=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') sign=-1;
else if(ch=='Q'||ch=='C') return ch;
ch=getchar();
}
while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
return ret*sign;
}
struct Cmd{
char op;
int x,y,z;
}cmd[maxn];
struct node{
int val,l,r,son[2];
node(){}
node(int _l,int _r){l=_l,r=_r,val=son[0]=son[1]=0;}
}T[maxn*400];
int root[maxn],cnt;
void ins(int op,int &u,int l,int r,int x){
if(!u) u=++cnt,T[u]=node(l,r);
T[u].val+=op;
int mid=(T[u].l+T[u].r)>>1;
if(l==r) return;
if(x<=mid) ins(op,T[u].son[0],l,mid,x);
else ins(op,T[u].son[1],mid+1,r,x);
}
inline int lbt(int x){return x&(-x);}
void add(int op,int u,int x){while(u<=n) ins(op,root[u],1,hashN,x),u+=lbt(u);}
int tmpP[2][20],rtN[2];
int query(int l,int r,int k){
rtN[0]=rtN[1]=0;
for(int i=l-1;i;i-=lbt(i)) tmpP[0][++rtN[0]]=root[i];
for(int i=r;i;i-=lbt(i)) tmpP[1][++rtN[1]]=root[i];
int vl=1,vr=hashN;
while(vl!=vr){
int mid=(vl+vr)>>1,lsum[2]={0},rela;
for(int i=0;i<=1;i++)
for(int j=1;j<=rtN[i];j++)
lsum[i]+=T[T[tmpP[i][j]].son[0]].val;
rela=k>lsum[1]-lsum[0];
if(rela) k-=lsum[1]-lsum[0],vl=mid+1;
else vr=mid;
for(int i=0;i<=1;i++)
for(int j=1;j<=rtN[i];j++)
tmpP[i][j]=T[tmpP[i][j]].son[rela];
}
return vl;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
hash[i]=a[i]=read();
hashN=n;
for(int i=1;i<=m;i++){
cmd[i].op=read();
if(cmd[i].op=='Q') cmd[i].x=read(),cmd[i].y=read(),cmd[i].z=read();
else cmd[i].x=read(),hash[++hashN]=cmd[i].y=read();
}
sort(hash+1,hash+hashN+1);
hashN=unique(hash+1,hash+hashN+1)-hash-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(hash+1,hash+hashN+1,a[i])-hash;
add(1,i,a[i]);
}
for(int i=1;i<=m;i++){
if(cmd[i].op=='Q') printf("%d\n",hash[query(cmd[i].x,cmd[i].y,cmd[i].z)]);
else cmd[i].y=lower_bound(hash+1,hash+hashN+1,cmd[i].y)-hash,add(-1,cmd[i].x,a[cmd[i].x]),add(1,cmd[i].x,cmd[i].y),a[cmd[i].x]=cmd[i].y;
}
return 0;
}
```
这个空间复杂度是可以优化的
用静态主席树维护原序列，空间复杂度 O(nlogn)
树状数组保存修改部分，树状数组每个元素内含一颗权值线段树，需要修改时动态加点，空间复杂度 O(mlognlogn)
查询时tmp1存当前到原树的结点，tmp2预处理出树状数组要修改的logn个结点，两部分加起来就是实际值
总空间复杂度 O(nlogn+mlognlogn) ，当m较小时效果明显
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10010;
int n,m,a[maxn];
int hash[maxn*2],hashN;
inline int read(){
int ret=0,sign=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') sign=-1;
if(ch=='Q'||ch=='C') return ch;
ch=getchar();
}
while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
return ret*sign;
}
struct Cmd{
char op;
int x,y,z;
}cmd[maxn];
struct node{
int val,son[2];
}T1[maxn*20],T2[maxn*400];
int root1[maxn],root2[maxn],cnt1,cnt2;
void build(int &u,int l,int r){
u=++cnt1;
if(l==r) return;
int mid=(l+r)>>1;
build(T1[u].son[0],l,mid);
build(T1[u].son[1],mid+1,r);
}
void ins1(int &u,int v,int l,int r,int x){
u=++cnt1,T1[u]=T1[v],++T1[u].val;
int mid=(l+r)>>1;
if(l==r) return;
if(x<=mid) ins1(T1[u].son[0],T1[v].son[0],l,mid,x);
else ins1(T1[u].son[1],T1[v].son[1],mid+1,r,x);
}
void ins2(int &u,int l,int r,int x,int op){
if(!u) u=++cnt2;
T2[u].val+=op;
int mid=(l+r)>>1;
if(l==r) return;
if(x<=mid) ins2(T2[u].son[0],l,mid,x,op);
else ins2(T2[u].son[1],mid+1,r,x,op);
}
inline int lbt(int x){return x&-x;}
inline void add(int u,int x,int op){while(u<=n) ins2(root2[u],1,hashN,x,op),u+=lbt(u);}
int tmp1[2],tmp2[2][20],tmpN[2];
int query(int l,int r,int k){
tmpN[0]=tmpN[1]=0;
tmp1[0]=root1[l-1],tmp1[1]=root1[r];
for(int i=l-1;i;i-=lbt(i)) tmp2[0][++tmpN[0]]=root2[i];
for(int i=r;i;i-=lbt(i)) tmp2[1][++tmpN[1]]=root2[i];
int vl=1,vr=hashN;
while(vl!=vr){
int lsum=T1[T1[tmp1[1]].son[0]].val-T1[T1[tmp1[0]].son[0]].val;
for(int i=1;i<=tmpN[0];i++)
lsum-=T2[T2[tmp2[0][i]].son[0]].val;
for(int i=1;i<=tmpN[1];i++)
lsum+=T2[T2[tmp2[1][i]].son[0]].val;
int rela=k>lsum;
if(rela) k-=lsum,vl=((vl+vr)>>1)+1;
else vr=(vl+vr)>>1;
tmp1[0]=T1[tmp1[0]].son[rela],tmp1[1]=T1[tmp1[1]].son[rela];
for(int i=1;i<=tmpN[0];i++)
tmp2[0][i]=T2[tmp2[0][i]].son[rela];
for(int i=1;i<=tmpN[1];i++)
tmp2[1][i]=T2[tmp2[1][i]].son[rela];
//cout<<vl<<' '<<vr<<endl;
}
return vl;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
hash[i]=a[i]=read();
hashN=n;
for(int i=1;i<=m;i++){
cmd[i].op=read();
if(cmd[i].op=='Q') cmd[i].x=read(),cmd[i].y=read(),cmd[i].z=read();
else cmd[i].x=read(),hash[++hashN]=cmd[i].y=read();
}
sort(hash+1,hash+hashN+1);
hashN=unique(hash+1,hash+hashN+1)-hash-1;
build(root1[0],1,hashN);
for(int i=1;i<=n;i++){
a[i]=lower_bound(hash+1,hash+hashN+1,a[i])-hash;
ins1(root1[i],root1[i-1],1,hashN,a[i]);
}
for(int i=1;i<=m;i++){
if(cmd[i].op=='Q') printf("%d\n",hash[query(cmd[i].x,cmd[i].y,cmd[i].z)]);
else{
cmd[i].y=lower_bound(hash+1,hash+hashN+1,cmd[i].y)-hash;
add(cmd[i].x,a[cmd[i].x],-1),add(cmd[i].x,cmd[i].y,1);
a[cmd[i].x]=cmd[i].y;
}
}
return 0;
}
```