题解 P2617 【Dynamic Ranking】
hzoi_mafia · · 题解
这题做法很多，最多的就是树状数组套主席树，这里就不再赘述，上个代码以示敬意
c++
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
int sum(0),f(1);
char ch(getchar());
for(;ch<'0'||ch>'9';ch=getchar())
if(ch=='-')
f=-1;
for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
return sum*f;
}
inline int lowbit(int x){
return x&-x;
}
int n,m;
int v[10005],num[20005];
int top,size,cnt;
int rt[10005],lch[20000005],rch[20000005],sum[20000005];
int A[10005],B[10005],K[10005];
int a,b,L[30],R[30];
bool flag[10005];
char op[2];
inline void update(int &x,int las,int pos,int w,int l,int r){
x=++cnt;
lch[x]=lch[las];
rch[x]=rch[las];
sum[x]=sum[las]+w;
if(l==r)return;
int mid((l+r)>>1);
if(pos<=mid)
update(lch[x],lch[las],pos,w,l,mid);
else
update(rch[x],rch[las],pos,w,mid+1,r);
}
inline int query(int l,int r,int k){
if(l==r)return l;
int mid((l+r)>>1),suml(0),sumr(0);
for(int i=1;i<=a;++i)
suml+=sum[lch[L[i]]];
for(int i=1;i<=b;++i)
sumr+=sum[lch[R[i]]];
if(k<=sumr-suml){
for(int i=1;i<=a;++i)
L[i]=lch[L[i]];
for(int i=1;i<=b;++i)
R[i]=lch[R[i]];
return query(l,mid,k);
}
else{
for(int i=1;i<=a;++i)
L[i]=rch[L[i]];
for(int i=1;i<=b;++i)
R[i]=rch[R[i]];
return query(mid+1,r,k-(sumr-suml));
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
v[i]=read();
num[++top]=v[i];
}
for(int i=1;i<=m;++i){
scanf("%s",op);
A[i]=read();
B[i]=read();
if(op[0]=='Q'){
flag[i]=1;
K[i]=read();
}
else
num[++top]=B[i];
}
sort(num+1,num+top+1);
size=unique(num+1,num+top+1)-num-1;
for(int i=1;i<=n;++i){
v[i]=lower_bound(num+1,num+top+1,v[i])-num;
for(int j=i;j<=n;j+=lowbit(j))
update(rt[j],rt[j],v[i],1,1,size);
}
for(int i=1;i<=m;++i){
if(flag[i]){
a=b=0;
--A[i];
for(int j=A[i];j;j-=lowbit(j))
L[++a]=rt[j];
for(int j=B[i];j;j-=lowbit(j))
R[++b]=rt[j];
printf("%d\n",num[query(1,size,K[i])]);
}
else{
int tmp(v[A[i]]);
for(int j=A[i];j<=n;j+=lowbit(j))
update(rt[j],rt[j],tmp,-1,1,size);
tmp=v[A[i]]=lower_bound(num+1,num+size+1,B[i])-num;
for(int j=A[i];j<=n;j+=lowbit(j))
update(rt[j],rt[j],tmp,1,1,size);
}
}
}然而肯定不止这种做法，比如说线段树套平衡树
我们建好一棵线段树，但线段树的每一个节点都是一棵平衡树，查询时二分权值查找，根据二分出的权值在区间中的排名进行二分边界的调整
c++
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
int sum(0),f(1);
char ch(getchar());
for(;ch<'0'||ch>'9';ch=getchar())
if(ch=='-')
f=-1;
for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
return sum*f;
}
#define get_size(x) (x?x->size:0)
struct node{
node *lch,*rch;
int size,key,fix;
node(int x=0):lch(NULL),rch(NULL),size(1),key(x),fix(rand()){}
inline void pushup(){
this->size=get_size(this->lch)+get_size(this->rch)+1;
}
}*tr[40005];
int n,m;
int a[10005];
char op[2];
inline void left_rotate(node *&x){
node *tmp(x->rch);
x->rch=tmp->lch;
tmp->lch=x;
x->pushup();
tmp->pushup();
x=tmp;
}
inline void right_rotate(node *&x){
node *tmp(x->lch);
x->lch=tmp->rch;
tmp->rch=x;
x->pushup();
tmp->pushup();
x=tmp;
}
inline void insert(node *&x,int v){
if(!x){
x=new node(v);
return;
}
if(v<=x->key){
insert(x->lch,v);
x->pushup();
if(x->lch->fix<x->fix)
right_rotate(x);
}
else{
insert(x->rch,v);
x->pushup();
if(x->rch->fix<x->fix)
left_rotate(x);
}
}
inline void del(node *&x,int v){
if(x->key==v){
if(x->lch&&x->rch){
if(x->lch->fix<x->rch->fix){
right_rotate(x);
del(x->rch,v);
}
else{
left_rotate(x);
del(x->lch,v);
}
}
else{
node *tmp(NULL);
if(x->lch)
tmp=x->lch;
else
tmp=x->rch;
delete x;
x=tmp;
}
}
else{
if(v<=x->key)
del(x->lch,v);
else
del(x->rch,v);
}
if(x)
x->pushup();
}
inline int Rank(node *now,int x){
int ret(0);
while(now){
if(x<=now->key)
now=now->lch;
else
ret+=get_size(now->lch)+1,now=now->rch;
}
return ret;
}
inline int kth(node *now,int k){
while(now){
if(get_size(now->lch)+1==k)
return now->key;
if(get_size(now->lch)+1>=k)
now=now->lch;
else
k-=get_size(now->lch)+1,now=now->rch;
}
}
inline void build(int l,int r,int rt){
for(int i=l;i<=r;++i)
insert(tr[rt],a[i]);
if(l==r)return;
int mid((l+r)>>1);
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
inline void update(int pos,int w,int l,int r,int i){
del(tr[i],a[pos]);
insert(tr[i],w);
if(l==r)return;
int mid((l+r)>>1);
if(pos<=mid)
update(pos,w,l,mid,i<<1);
else
update(pos,w,mid+1,r,i<<1|1);
}
inline int Rank(int ll,int rr,int x,int l,int r,int i){
if(ll<=l&&r<=rr)
return Rank(tr[i],x);
int mid((l+r)>>1),ret(0);
if(ll<=mid)
ret+=Rank(ll,rr,x,l,mid,i<<1);
if(mid<rr)
ret+=Rank(ll,rr,x,mid+1,r,i<<1|1);
return ret;
}
inline int query(int l,int r,int k){
int ll(1),rr(1e9);
while(ll<=rr){
int mid((ll+rr)>>1);
int jud(Rank(l,r,mid,1,n,1));
if(jud<k)
ll=mid+1;
else
rr=mid-1;
}
return rr;
}
int main(){
srand(time(NULL));
n=read(),m=read();
for(int i=1;i<=n;++i)
a[i]=read();
build(1,n,1);
while(m--){
scanf("%s",op);
if(op[0]=='Q'){
int x(read()),y(read()),k(read());
printf("%d\n",query(x,y,k));
}
else{
int x(read()),y(read());
update(x,y,1,n,1);
a[x]=y;
}
}
}两种做法比较：
树状数组套主席树：103行 代码长度 2.2KB 时间 232ms 内存 26.21MB（可能是我开大了QAQ） 打代码时间 10min~15min
线段树套平衡树：171行 代码长度 3.07KB 时间 640ms 内存 8.72MB（动态开内存比较准） 打代码时间 15min~20min（应该用不到20min吧，可能是我没打熟QAQ）