定一个含有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继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
写了一个树状数组套主席树的做法 nlog^2n, 还有一个节省空间但是耗时间的算法是线段树套平衡树，nlog^3n
沉迷数据结构
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MN 2000000
#define MM 10000
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
}
char op[];
int rt[MM*+],n,m,cnt,tot,l2[MM*+],s[MM+],c[],cnum,b[],bnum;
struct Segment_Tree{
int l,r,x;
}T[MN+];
struct ques{
int kind,l,r,v;
}q[MM+]; void ins(int x,int v,int ad,int l=,int r=tot)
{
T[x].x+=ad;
if(l==r) return;
int mid=l+r>>;
if(v<=mid) ins(T[x].l?T[x].l:(T[x].l=++cnt),v,ad,l,mid);
else ins(T[x].r?T[x].r:(T[x].r=++cnt),v,ad,mid+,r);
} void renew(int x,int v,int ad)
{
for(;x<=tot;x+=x&(-x))
ins(rt[x],v,ad);
} int main()
{
tot=n=read();m=read();
for(int i=;i<=n;i++) l2[i]=s[i]=read();
for(int i=;i<=m;i++)
{
scanf("%s",op);q[i].l=read();
q[i].r=read();
if(op[]=='Q') q[i].kind=,q[i].v=read();
else q[i].kind=,l2[++tot]=q[i].r;
}
sort(l2+,l2+tot+);
for(int i=;i<=tot;i++) rt[i]=i;cnt=tot;
for(int i=;i<=n;i++)
{
s[i]=lower_bound(l2+,l2+tot+,s[i])-l2;
renew(i,s[i],);
}
for(int i=;i<=m;i++)
{
if(q[i].kind==)
{
q[i].r=lower_bound(l2+,l2+tot+,q[i].r)-l2;
renew(q[i].l,s[q[i].l],-);
renew(q[i].l,q[i].r,);
s[q[i].l]=q[i].r;
}
else
{
int l=,r=tot,mid;cnum=bnum=;
for(int j=q[i].r;j;j-=j&(-j))c[++cnum]=rt[j];
for(int j=q[i].l-;j;j-=j&(-j)) b[++bnum]=rt[j];
while(l<=r)
{
mid=l+r>>;int x=;
for(int j=;j<=cnum;j++) x+=T[T[c[j]].l].x;
for(int j=;j<=bnum;j++) x-=T[T[b[j]].l].x;
if(x>=q[i].v)
{
r=mid;
for(int j=;j<=cnum;j++) c[j]=T[c[j]].l;
for(int j=;j<=bnum;j++) b[j]=T[b[j]].l;
}
else
{
l=mid+;q[i].v-=x;
for(int j=;j<=cnum;j++) c[j]=T[c[j]].r;
for(int j=;j<=bnum;j++) b[j]=T[b[j]].r;
}
}
printf("%d\n",l2[r]);
}
}
return ;
}
线段树套平衡树 结果我一不小心写成了树状数组 空间nlogn 时间nlog^3n
一开始把重建操作注释掉了交上去居然也过了，BST最棒啦，垃圾替罪羊
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MN 400000
#define MM 10000
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
}
char op[];
int rt[MM*+],n,m,cnt,mark=,tot,top=,l2[MM*+],s[MM+];
int c[MN+][],size[MN+],num[MN+],nn[MN+],fa[MN+],qx[MN+];
struct ques{
int kind,l,r,v;
}q[MM+]; void ins(int&x,int v,int ad,int last)
{
//cout<<"ins"<<x<<" "<<v<<" "<<ad<<" "<<last<<endl;
if(!x){x=++cnt;nn[x]=v;num[x]=;size[x]=;fa[x]=last;return;}
if(v==nn[x]){num[x]+=ad;size[x]+=ad;return;}
if(v<nn[x]) ins(c[x][],v,ad,x);
else ins(c[x][],v,ad,x);
size[x]=size[c[x][]]+size[c[x][]]+num[x];
if(max(size[c[x][]],size[c[x][]])>=0.7*size[x]) mark=x;
} void dfs(int x)
{
if(c[x][]) dfs(c[x][]);
if(num[x])qx[++top]=x;
if(c[x][]) dfs(c[x][]);
fa[x]=c[x][]=c[x][]=;
} void build(int&x,int l,int r,int last)
{
if(l>r) {x=;return;}int mid=l+r>>;
x=qx[mid];fa[x]=last;
build(c[x][],l,mid-,x);
build(c[x][],mid+,r,x);
size[x]=size[c[x][]]+size[c[x][]]+num[x];
} void rebuild(int i)
{
top=;int y=fa[mark];dfs(mark);
if(!y) build(rt[i],,top,);
else build(c[y][c[y][]==mark],,top,y);
mark=;
} void renew(int x,int v,int ad)
{
for(;x<=tot;x+=x&(-x))
{
ins(rt[x],v,ad,);
if(mark) rebuild(x);
}
} int query(int x,int k)
{
if(!x) return ;
if(nn[x]>=k) return query(c[x][],k)+((nn[x]==k)?num[x]:);
else return size[c[x][]]+num[x]+query(c[x][],k);
} int check(int x,int v)
{
int sum=;
for(;x;x-=x&(-x))
sum+=query(rt[x],v);
return sum;
} int main()
{
tot=n=read();m=read();
for(int i=;i<=n;i++) l2[i]=s[i]=read();
for(int i=;i<=m;i++)
{
scanf("%s",op);q[i].l=read();
q[i].r=read();
if(op[]=='Q') q[i].kind=,q[i].v=read();
else q[i].kind=,l2[++tot]=q[i].r;
}
sort(l2+,l2+tot+);
for(int i=;i<=n;i++)
{
s[i]=lower_bound(l2+,l2+tot+,s[i])-l2;
renew(i,s[i],);
}
for(int i=;i<=m;i++)
{
if(q[i].kind==)
{
q[i].r=lower_bound(l2+,l2+tot+,q[i].r)-l2;
renew(q[i].l,s[q[i].l],-);
renew(q[i].l,q[i].r,);
s[q[i].l]=q[i].r;
}
else
{
int l=,r=tot,mid,ans=;
while(l<=r)
{
mid=l+r>>;
int x=check(q[i].r,mid)-check(q[i].l-,mid);
//cout<<l2[mid]<<" "<<check(q[i].r,mid)<<" "<<check(q[i].l-1,mid)<<endl;
if(x>=q[i].v) ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",l2[ans]);
}
}
return ;
}