BZOJ 1901 Zju2112 Dynamic Rankings ——树状数组套主席树
【题目分析】
BZOJ这个题目抄的挺霸气。
主席树是第一时间想到的，但是修改又很麻烦。
看了别人的题解，原来还是可以用均摊的思想，用树状数组套主席树。
学到了新的姿势，2333o(*￣▽￣*)ブ
【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define maxn 20005
#define mlog 16
#define inf (0x3f3f3f3f)
int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int rt[maxn],ls[maxn*mlog*mlog],rs[maxn*mlog*mlog],siz[maxn*mlog*mlog];
int a[maxn],b[maxn],n,m,top=0,tot=0;
int opt[maxn],x[maxn],y[maxn],z[maxn],L[mlog],R[mlog];
char s[11];
void ins(int o1,int & o2,int l,int r,int x,int f)
{
// printf("ins %d %d %d %d %d %d\n",o1,o2,l,r,x,f);
o2=++tot;
siz[o2]=siz[o1]+f;
if (l==r) return ;
int mid=(l+r)/2;
if (x<=mid) rs[o2]=rs[o1],ins(ls[o1],ls[o2],l,mid,x,f);
else ls[o2]=ls[o1],ins(rs[o1],rs[o2],mid+1,r,x,f);
return ;
}
int query(int l,int r,int x)
{
// printf("query %d %d %d\n",l,r,x);
if (l==r) return l;
int mid=(l+r)/2,tmp=0;
for (int i=1;i<=L[0];++i) tmp-=siz[ls[L[i]]];
for (int i=1;i<=R[0];++i) tmp+=siz[ls[R[i]]];
// printf("tmp is %d\n",tmp);
if (x<=tmp)
{
for (int i=1;i<=L[0];++i) L[i]=ls[L[i]];
for (int i=1;i<=R[0];++i) R[i]=ls[R[i]];
return query(l,mid,x);
}
else
{
for (int i=1;i<=L[0];++i) L[i]=rs[L[i]];
for (int i=1;i<=R[0];++i) R[i]=rs[R[i]];
return query(mid+1,r,x-tmp);
}
}
int main()
{
top=n=read();m=read();
for (int i=1;i<=n;++i) b[i]=a[i]=read();
for (int i=1;i<=m;++i)
{
scanf("%s",s);
switch(s[0])
{
case 'Q': opt[i]=0;x[i]=read();x[i]--;y[i]=read();z[i]=read();break;
case 'C': opt[i]=1;x[i]=read();y[i]=read();b[++top]=y[i];break;
}
}
sort(b+1,b+top+1);
top=unique(b+1,b+top+1)-b-1;
for (int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+top+1,a[i])-b;
for (int i=1;i<=m;++i) if (opt[i]) y[i]=lower_bound(b+1,b+top+1,y[i])-b;
// printf("lisan is OK!\n");
// for (int i=1;i<=n;++i) printf("%d ",a[i]); printf("\n");
// for (int i=1;i<=m;++i) printf("%d ",y[i]); printf("\n");
for (int i=1;i<=n;++i)
{
// printf("ins %d %d\n",a[i],i);getchar();
for (int j=i;j<=n;j+=j&(-j))
ins(rt[j],rt[j],1,top,a[i],1);
}
for (int i=1;i<=m;++i)
{
if (opt[i])
{
// printf("fix %d to %d\n",x[i],y[i]);
for (int j=x[i];j<=n;j+=j&(-j))
{
ins(rt[j],rt[j],1,top,a[x[i]],-1);
ins(rt[j],rt[j],1,top,y[i],1);
}
a[x[i]]=y[i];
}
else
{
// printf("query %d %d %d \n",x[i],y[i],z[i]);
L[0]=0; R[0]=0;
for (int j=x[i];j;j-=j&(-j)) L[++L[0]]=rt[j];
for (int j=y[i];j;j-=j&(-j)) R[++R[0]]=rt[j];
// printf("L :"); for (int j=1;j<=L[0];++j) printf("%d ",L[i]);
// printf("R :"); for (int j=1;j<=R[0];++j) printf("%d ",R[i]);
printf("%d\n",b[query(1,top,z[i])]);
}
}
}