bzoj1901&zoj2112&cogs257 Dynamic Rankings(动态排名系统)

---

cogs

zoj

bzoj-权限

---

题解

bzoj和zoj都是骗访问量的233，我没有权限

带修改区间k小值，看了学习了题解一次AC真开心。。。

不带修改的是前缀和套主席树，\(O(log_2n)\)查询，要修改只能\(O(nlog_2n)\)乱搞。

把外层前缀和改成树状数组，即第\(i\)个主席树从存\(1\) ~ \(i\)的值域改成存\(i-lowbit(i)+1\) ~ \(i\)的值域。然后修改和查询都是\(O(log_2^2n)\)的。。。（一个\(log\)树状数组另一个线段树）

查询就从两个根相减变成多个根减多个根了，和bit差不多。

---

Code

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "dynrank"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

#define lb(o) ((o)&(-(o)))

#define mid ((l+r)>>1)

typedef long long ll;

il int gi(){

    rg int x=0;rg char ch=getchar();

    while(ch<'0'||ch>'9')ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x;

}

typedef struct node* point;

point null;

struct node{

    int data;

    point ls,rs;

    node(){ls=rs=null,data=0;}

    node(point _ls,point _rs){ls=_ls,rs=_rs,data=0;}

};

const int maxn=50001,maxm=10001;

il vd copy(point&a,point b){

    if(b==null)a=null;

    else a=new node,*a=*b;

}

il vd Updata(point&s,point rt,int l,int r,int&pos,int num){

    copy(s,rt);

    s->data+=num;

    if(l==r)return;

    if(mid<pos)Updata(s->rs,rt->rs,mid+1,r,pos,num);

    else Updata(s->ls,rt->ls,l,mid,pos,num);

}

il point build(int l,int r){

    if(l==r)return new node;

    return new node(build(l,mid),build(mid+1,r));

}

point a[18],b[18];

int _a,_b;

il int Query(int l,int r,int k){

    while(l<r){

	int res=0;

	rep(i,1,_a)res+=a[i]->ls->data;

	rep(i,1,_b)res-=b[i]->ls->data;

	if(res>=k){

	    rep(i,1,_a)a[i]=a[i]->ls;

	    rep(i,1,_b)b[i]=b[i]->ls;

	    r=mid;

	}else{

	    rep(i,1,_a)a[i]=a[i]->rs;

	    rep(i,1,_b)b[i]=b[i]->rs;

	    l=mid+1,k-=res;

	}

    }return l;

}

il vd free(point i){if(i!=null)free(i->ls),free(i->rs),delete i;}

il vd work(){

    int n=gi(),m=gi(),N=n;

    point root[maxn+maxm];

    int num[maxn],data[maxn+maxm];

    int A[maxm],B[maxm],K[maxm];

    char opt[3];

    rep(i,1,n)num[i]=data[i]=gi();

    rep(i,1,m){

	scanf("%s",opt);

	A[i]=gi(),B[i]=gi();

	if(opt[0]=='Q')K[i]=gi();

	else K[i]=-1,data[++N]=B[i];

    }

    sort(data+1,data+N+1);

    int tot=unique(data+1,data+N+1)-data-1;

    root[0]=build(1,tot);

    rep(i,1,n)num[i]=lower_bound(data+1,data+tot+1,num[i])-data,root[i]=root[i-1];

    rep(i,1,n)for(rg int j=i;j<=n;j+=lb(j))Updata(root[j],root[j],1,tot,num[i],1);

    rep(i,1,m){

	if(K[i]==-1){

	    B[i]=lower_bound(data+1,data+tot+1,B[i])-data;

	    for(rg int j=A[i];j<=n;j+=lb(j))Updata(root[j],root[j],1,tot,num[A[i]],-1);

	    num[A[i]]=B[i];

	    for(rg int j=A[i];j<=n;j+=lb(j))Updata(root[j],root[j],1,tot,num[A[i]],1);

	}else{

	    _a=_b=0;

	    for(rg int j=B[i];j;j-=lb(j))a[++_a]=root[j];

	    for(rg int j=A[i]-1;j;j-=lb(j))b[++_b]=root[j];

	    printf("%d\n",data[Query(1,tot,K[i])]);

	}

    }

}

int main(){

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    int T=gi();

    null=new node;

    null->ls=null->rs=null;

    while(T--)work();

    return 0;

}