正文
bzoj1901：Zju2112 Dynamic Rankings
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
思路：树套树，我写了两种，一种是线段树套splay，线段树维护区间信息，splay维护第k大，一种是树状数组套权值线段树（并不是什么可持久化线段树，只不过是动态开点罢了，为什么网上一大堆题解都是可持久化线段树。。。。。明明可以直接修改的，不过可持久化线段树应该也是可以写的），树状数组维护前缀和，权值线段树维护第k大，利用那道不带修改的裸题的思想即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 10005 int n,m;
int a[maxn];
char s[3]; inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
} struct splay_tree{
int ch[200*maxn][2],fa[200*maxn],note[200*maxn],val[200*maxn],size[200*maxn],cover[200*maxn],tot;
void clear(){
memset(val,-1,sizeof(val));
}
void update(int x){
if (!x) return;
size[x]=size[ch[x][0]]+size[ch[x][1]]+cover[x];
}
void rotate(int x){
int y=fa[x],z=fa[y],bo=note[x],bo1=note[y];
ch[y][bo]=ch[x][bo^1],fa[ch[x][bo^1]]=y;
ch[x][bo^1]=y,fa[y]=x;
fa[x]=z;if (z) ch[z][bo1]=x;
note[x]=bo1,note[y]=bo^1,note[ch[y][bo]]=bo;
update(y);
}
void splay(int x){
while (note[x]!=2){
if (note[x]==note[fa[x]]) rotate(fa[x]);
rotate(x);
}
update(x);
}
void insert(int &x,int v){
int y;
while (1){
if (val[x]==v){cover[x]++,y=x;break;}
y=ch[x][val[x]<v];
if (!y){
y=++tot;
val[y]=v,size[y]=1,cover[y]=1;
if (x) note[y]=(val[x]<v);else note[y]=2;
fa[y]=x,ch[y][0]=ch[y][1]=0;
if (x) ch[x][note[y]]=y;
break;
}
x=y;
}
splay(y),x=y;
}
int find(int x,int v){
splay(x);
while (1){
if (val[x]==v) return x;
else if (val[x]<v) x=ch[x][1];
else x=ch[x][0];
}
}
int findk(int x,int v){
splay(x);int ans=0;
while (x){
if (v<val[x]) x=ch[x][0];
else if (v==val[x]) return ans+size[ch[x][0]]+cover[x];
else ans+=size[ch[x][0]]+cover[x],x=ch[x][1];
}
return ans;
}
int suc(int x){
splay(x);
int tmp=ch[x][1];
while (ch[tmp][0]) tmp=ch[tmp][0];
return tmp;
}
void del(int &rt,int x){
if (cover[x]>1){
splay(x);rt=x;
cover[x]--,size[x]--;
return;
}
splay(x);int y=suc(x),z=ch[x][0];
if (!y){
if (!z){rt=0;return;}
fa[z]=0,note[z]=2,rt=z;return;
}
fa[ch[x][1]]=0,note[ch[x][1]]=2,splay(y);
ch[y][0]=z,fa[z]=y,update(y),rt=y;
}
}S; struct segment_tree{
struct treenode{
int root;
}tree[6*maxn];
void build(int p,int l,int r){
for (int i=l;i<=r;i++) S.insert(tree[p].root,a[i]);
if (l==r) return;
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int pos,int val){
S.del(tree[p].root,S.find(tree[p].root,a[pos])),S.insert(tree[p].root,val);
if (l==r) return;
int mid=(l+r)>>1;
if (pos<=mid) change(p<<1,l,mid,pos,val);
else change(p<<1|1,mid+1,r,pos,val);
}
int query(int p,int l,int r,int x,int y,int v){
if (x<=l && r<=y) return S.findk(tree[p].root,v);
int mid=(l+r)>>1,ans=0;
if (x<=mid) ans+=query(p<<1,l,mid,x,y,v);
if (y>mid) ans+=query(p<<1|1,mid+1,r,x,y,v);
return ans;
}
}T; int main(){
n=read(),m=read();S.clear();
for (int i=1;i<=n;i++) a[i]=read();
T.build(1,1,n);
while (m--){
scanf("%s",s+1);int aa=read(),b=read();
if (s[1]=='C') T.change(1,1,n,aa,b),a[aa]=b;
else{
int k=read();int l=-1e9-7,r=1e9+7,ans=0;
while (l<=r){
int mid=(l+r)>>1;
if (T.query(1,1,n,aa,b,mid)<k) l=mid+1;
else r=mid-1,ans=mid;
}
printf("%d\n",ans);
}
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 100005 int n,Q,tot,top1,top2,maxv;
int a[maxn],t1[maxn],t2[maxn];
char s[2]; struct node{
int val,pos;
bool operator <(const node &a)const{return val<a.val;}
}b[maxn],c[maxn]; struct query{
int type,a,b,c;
}q[maxn]; bool cmp(node a,node b){return a.pos<b.pos;} struct segment_tree{
int root[maxn],treedeg;
struct node{
int sum,ls,rs;
}tree[10*maxn];
void change(int &p,int l,int r,int pos,int val){
if (!p) p=++treedeg;int mid=(l+r)>>1;
tree[p].sum+=val;
if (l==r) return;
if (pos<=mid) change(tree[p].ls,l,mid,pos,val);
else change(tree[p].rs,mid+1,r,pos,val);
}
}T; void change(int i,int pos,int val){
for (;i<=n;i+=i&(-i)) T.change(T.root[i],1,maxv,pos,val);
} void query(int x,int y,int rank){
top1=top2=0;
for (int i=x;i;i-=i&(-i)) t1[++top1]=T.root[i];
for (int i=y;i;i-=i&(-i)) t2[++top2]=T.root[i];
int l=1,r=maxv;
while (l<r){
int sum=0,mid=(l+r)>>1;
for (int i=1;i<=top1;i++) sum+=T.tree[T.tree[t1[i]].ls].sum;
for (int i=1;i<=top2;i++) sum-=T.tree[T.tree[t2[i]].ls].sum;
if (sum>=rank){
for (int i=1;i<=top1;i++) t1[i]=T.tree[t1[i]].ls;
for (int i=1;i<=top2;i++) t2[i]=T.tree[t2[i]].ls;
r=mid;
}
else{
for (int i=1;i<=top1;i++) t1[i]=T.tree[t1[i]].rs;
for (int i=1;i<=top2;i++) t2[i]=T.tree[t2[i]].rs;
l=mid+1,rank-=sum;
}
}
printf("%d\n",b[l].val);
} int main(){
scanf("%d%d",&n,&Q);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i].val=a[i],b[i].pos=i;int tmp=n;
for (int i=1;i<=Q;i++){
scanf("%s%d%d",s+1,&q[i].a,&q[i].b),q[i].type=(s[1]=='C'?0:1);
if (q[i].type) scanf("%d",&q[i].c);else b[++tmp].val=q[i].b,b[tmp].pos=n+i;
}
sort(b+1,b+tmp+1),sort(a+1,a+n+1);
for (int i=1;i<=tmp;i++)
if (b[i].pos>n) q[b[i].pos-n].b=i;
else c[++tot].val=i,c[tot].pos=b[i].pos;
sort(c+1,c+tot+1,cmp);maxv=tmp;
for (int i=1;i<=n;i++) change(i,c[i].val,1);
for (int i=1;i<=Q;i++){
if (q[i].type==0){
int pos=q[i].a,val=q[i].b;
change(pos,c[pos].val,-1),change(pos,val,1),c[pos].val=val;
}
else query(q[i].b,q[i].a-1,q[i].c);
}
return 0;
}
