Lvat_s Blog

这是我第一次写树状数组套可持久化数据结构，写了好长时间……

首先你需要AC POJ2104

然后把一个个递增的版本用树状数组维护就好了

为什么呢？因为你维护的是权值线段树，需要得到的值其实是作差得来的。

那么我们用类似树状数组的作差方法就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int siz,n,m,a[10005],tab[500005],tb,root[10005],A[10005],B[10005],An,Bn;

struct SegTree{
int nl,nr,sum;
}tree[2000005];

struct Ask{
int opt,l,r,k;
}ask[10005];

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

int Div(int x){
int l=1,r=tb;
while(l<=r){
	int mid=l+r>>1;
	if(tab[mid]<x)l=mid+1;
	else r=mid-1;
}
return l;
}

void AddTree(int lastrt,int l,int r,int &rt,int pos,int val){
if(rt==0)rt=++siz;
tree[rt].sum=tree[lastrt].sum+val;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
if(l==r)return;
int mid=l+r>>1;
if(pos<=mid)AddTree(tree[lastrt].nl,l,mid,tree[rt].nl,pos,val);
else AddTree(tree[lastrt].nr,mid+1,r,tree[rt].nr,pos,val);
}

int Sum(int l,int r,int k){
if(l==r)return l;
int sumL=0,sumR=0,mid=l+r>>1;
for(int i=1;i<=An;i++)sumL+=tree[tree[A[i]].nl].sum;
for(int i=1;i<=Bn;i++)sumR+=tree[tree[B[i]].nl].sum;
if(sumR-sumL>=k){
	for(int i=1;i<=An;i++)A[i]=tree[A[i]].nl;
	for(int i=1;i<=Bn;i++)B[i]=tree[B[i]].nl;
	return Sum(l,mid,k);
}
else {
	for(int i=1;i<=An;i++)A[i]=tree[A[i]].nr;
	for(int i=1;i<=Bn;i++)B[i]=tree[B[i]].nr;
	return Sum(mid+1,r,k-sumR+sumL);
}
}

int main(){
freopen("1901.in","r",stdin);
freopen("1901.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
	scanf("%d",&a[i]);
	tab[++tb]=a[i];
}
for(int i=1;i<=m;i++){
	char s[5];
    scanf("%s",s);
    if(s[0]=='C'){
		scanf("%d %d",&ask[i].l,&ask[i].k);
        ask[i].opt=1;
        tab[++tb]=ask[i].k;
    }
    if(s[0]=='Q'){
		scanf("%d %d %d",&ask[i].l,&ask[i].r,&ask[i].k);
		ask[i].opt=2;
		ask[i].l--;
    }
}
sort(tab+1,tab+tb+1);
tb=unique(tab+1,tab+tb+1)-tab-1;
for(int i=1;i<=n;i++){
    int x=Div(a[i]);
    for(int j=i;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,1);
}
for(int i=1;i<=m;i++){
	if(ask[i].opt==1){
		int x=Div(a[ask[i].l]);
		for(int j=ask[i].l;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,-1);
        a[ask[i].l]=ask[i].k;
        x=Div(ask[i].k);
		for(int j=ask[i].l;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,1);
	}
	else {
		An=Bn=0;
		for(int j=ask[i].l;j;j-=lowbit(j))A[++An]=root[j];
		for(int j=ask[i].r;j;j-=lowbit(j))B[++Bn]=root[j];
		printf("%d\n",tab[Sum(1,tb,ask[i].k)]);
	}
}
return 0;
}