【BZOJ1901】Dynamic Rankings – 徐亦轲的博客

树状数组套主席树裸题

~~等下上课就要讲了啊。。。赶快传上来先~~

好了可以开写了~~虽然还没讲~~

其实这个东西很简单的。。

因为操作要求单点修改单点查询

主席树原本用的是前缀和，查询O(1)修改O(n)

啥都不用是查询O(n)修改O(1)

【很自然的】就想到折中的树状数组了

于是就完了

// <1901.cpp> - 01/26/16 20:51:46
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=10001;
int lowbit(int x){return x&-x;}
int val[40*MAXN],l[40*MAXN],r[40*MAXN];
int a[MAXN],u[MAXN*2],root[MAXN];
int A[MAXN],B[MAXN],C[MAXN];
int ls,rs,LS[30],RS[30];
int tot;
int ref(int root,int L,int R,int rank,int x){
	int now=++tot;
	val[now]=val[root]+x;l[now]=l[root];r[now]=r[root];
	if(L!=R){
		int M=(L+R)>>1;
		if(rank<=M)l[now]=ref(l[root],L,M,rank,x);
		else r[now]=ref(r[root],M+1,R,rank,x);
	}
	return now;
}
int src(int L,int R,int k){
	if(L==R)return L;
	int suml=0,sumr=0;
	for(int i=1;i<=ls;i++)suml+=val[l[LS[i]]];
	for(int i=1;i<=rs;i++)sumr+=val[l[RS[i]]];
	int M=(L+R)>>1;
	if(k<=sumr-suml){
		for(int i=1;i<=ls;i++)LS[i]=l[LS[i]];
		for(int i=1;i<=rs;i++)RS[i]=l[RS[i]];
		return src(L,M,k);
	}else{
		for(int i=1;i<=ls;i++)LS[i]=r[LS[i]];
		for(int i=1;i<=rs;i++)RS[i]=r[RS[i]];
		return src(M+1,R,k-(sumr-suml));
	}
}
int main(){
	int n=getint(),m=getint(),L=n;
	char s;
	for(int i=1;i<=n;i++)u[i]=a[i]=getint();
	for(int i=1;i<=m;i++){
		cin>>s;
		A[i]=getint();B[i]=getint();
		if(s=='Q')C[i]=getint();
		else u[++L]=B[i];
	}
	sort(u+1,u+1+L);
	L=unique(u+1,u+1+L)-u-1;
	for(int i=1;i<=n;i++){
		int rank=lower_bound(u+1,u+1+L,a[i])-u;
		for(int o=i;o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,1);
	}
	for(int i=1;i<=m;i++){
		if(C[i]){
			ls=0;rs=0;A[i]--;
			for(int o=A[i];o;o-=lowbit(o))LS[++ls]=root[o];
			for(int o=B[i];o;o-=lowbit(o))RS[++rs]=root[o];
			printf("%d\n",u[src(1,L,C[i])]);
		}else{
			int rank=lower_bound(u+1,u+1+L,a[A[i]])-u;
			a[A[i]]=B[i];
			for(int o=A[i];o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,-1);
			rank=lower_bound(u+1,u+1+L,B[i])-u;
			for(int o=A[i];o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,1);
		}
	}
	return 0;
}

// <1901.cpp> - 01/26/16 20:51:46

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

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

if(ch=='-')fh=-1,ch=getchar();

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

return fh*res;

}

const int MAXN=10001;

int lowbit(int x){return x&-x;}

int val[40*MAXN],l[40*MAXN],r[40*MAXN];

int a[MAXN],u[MAXN*2],root[MAXN];

int A[MAXN],B[MAXN],C[MAXN];

int ls,rs,LS[30],RS[30];

int tot;

int ref(int root,int L,int R,int rank,int x){

int now=++tot;

val[now]=val[root]+x;l[now]=l[root];r[now]=r[root];

if(L!=R){

int M=(L+R)>>1;

if(rank<=M)l[now]=ref(l[root],L,M,rank,x);

else r[now]=ref(r[root],M+1,R,rank,x);

}

return now;

}

int src(int L,int R,int k){

if(L==R)return L;

int suml=0,sumr=0;

for(int i=1;i<=ls;i++)suml+=val[l[LS[i]]];

for(int i=1;i<=rs;i++)sumr+=val[l[RS[i]]];

int M=(L+R)>>1;

if(k<=sumr-suml){

for(int i=1;i<=ls;i++)LS[i]=l[LS[i]];

for(int i=1;i<=rs;i++)RS[i]=l[RS[i]];

return src(L,M,k);

}else{

for(int i=1;i<=ls;i++)LS[i]=r[LS[i]];

for(int i=1;i<=rs;i++)RS[i]=r[RS[i]];

return src(M+1,R,k-(sumr-suml));

}

int main(){

int n=getint(),m=getint(),L=n;

char s;

for(int i=1;i<=n;i++)u[i]=a[i]=getint();

for(int i=1;i<=m;i++){

cin>>s;

A[i]=getint();B[i]=getint();

if(s=='Q')C[i]=getint();

else u[++L]=B[i];

}

sort(u+1,u+1+L);

L=unique(u+1,u+1+L)-u-1;

for(int i=1;i<=n;i++){

int rank=lower_bound(u+1,u+1+L,a[i])-u;

for(int o=i;o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,1);

}

for(int i=1;i<=m;i++){

if(C[i]){

ls=0;rs=0;A[i]--;

for(int o=A[i];o;o-=lowbit(o))LS[++ls]=root[o];

for(int o=B[i];o;o-=lowbit(o))RS[++rs]=root[o];

printf("%d\n",u[src(1,L,C[i])]);

}else{

int rank=lower_bound(u+1,u+1+L,a[A[i]])-u;

a[A[i]]=B[i];

for(int o=A[i];o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,-1);

rank=lower_bound(u+1,u+1+L,B[i])-u;

for(int o=A[i];o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,1);

}

return 0;

}