BZOJ_1901_Zju2112 Dynamic Rankings_树状数组+主席树

题意：

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改

变后的a继续回答上面的问题。

分析：

区间第k小，可以用主席树维护

然而有修改，每次修改都会对后面的线段树有影响

因为一般的主席树是前缀和的思想

不妨用树状数组维护可持久化线段树

查询和修改都乘上个logn

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100500

int t[N*40],ls[N*40],rs[N*40],n,m,root[N*40];

int sx[N],sy[N],v[N],maxn=1000000000,cnt,lx,ly;

char ch[10];

void insert(int x,int &y,int l,int r,int val,int c){

	if(!y)y=++cnt;

	if(l==r) { t[y] = t[x] + c; return ;}

	int mid=l+r>>1;

	if(val<=mid) rs[y]=rs[x],insert(ls[x],ls[y],l,mid,val,c);

	else ls[y]=ls[x],insert(rs[x],rs[y],mid+1,r,val,c);

	t[y] = t[ls[y]] + t[rs[y]];

}

int query(int l,int r,int k){

	if(l==r)return l;

	int sizls=0,mid=l+r>>1,i;

	for(i=1;i<=ly;i++) sizls += t[ls[sy[i]]];

	for(i=1;i<=lx;i++) sizls -= t[ls[sx[i]]];

	if(k<=sizls){

		for(i=1;i<=ly;i++) sy[i]=ls[sy[i]];

		for(i=1;i<=lx;i++) sx[i]=ls[sx[i]];

		return query(l,mid,k);

	}else{

		for(i=1;i<=ly;i++) sy[i]=rs[sy[i]];

		for(i=1;i<=lx;i++) sx[i]=rs[sx[i]];

		return query(mid+1,r,k-sizls);

	}

}

int main(){

	scanf("%d%d",&n,&m);

	int i,x,y,z,tot=n,j,k;

	for(i=1;i<=n;i++) { scanf("%d",&v[i]);for(j=i;j<=n;j+=j&(-j))insert(root[j],root[j],0,maxn,v[i],1); }

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

		scanf("%s%d%d",ch,&x,&y);

		if(ch[0]=='C'){

			for(j=x;j<=n;j+=j&(-j)) insert(root[j],root[j],0,maxn,v[x],-1);

			v[x]=y;

			for(j=x;j<=n;j+=j&(-j)) insert(root[j],root[j],0,maxn,v[x],1);

		}else{

			scanf("%d",&z);

			for(lx=0,j=x-1;j;j-=j&(-j)) sx[++lx] = root[j];

			for(ly=0,j=y;j;j-=j&(-j)) sy[++ly] = root[j];

			printf("%d\n",query(0,maxn,z));

		}

	}

}

巴特西

BZOJ_1901_Zju2112 Dynamic Rankings_树状数组+主席树

最新文章

热门文章