题目描述
给定一个含有 (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)继续回答上面的问题。
输入格式
第一行有两个正整数(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 m,n≤10000)
输出格式
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
样例
样例输入
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
样例输出
3
6
分析
对于静态的区间第 (k) 大，我们利用前缀和的思想用主席树解决
对于动态的区间第 (k) 大，如果我们去暴力修改前缀和，时间复杂度(nlogn)是无法接受的
我们可以用树状数组优化这个过程，每次只修改 (logn) 颗线段树
这样可以做到单次修改 (logn^2) 的复杂度
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
inline int lb(int xx){
return xx&-xx;
}
int sta[maxn<<1],tp=0,n,m,a[maxn],rt[maxn],cnt,jl[2][22],cnt0,cnt1;
struct jie{
char op;
int ac1,ac2,ac3;
jie(){}
jie(char aa,int bb,int cc,int dd){
op=aa,ac1=bb,ac2=cc,ac3=dd;
}
}b[maxn];
struct trr{
int l,r,lch,rch,val;
}tr[maxn<<4];
int build(int da,int l,int r){
da=++cnt;
tr[da].l=l,tr[da].r=r;
if(tr[da].l==tr[da].r){
return da;
}
rg int mids=(tr[da].l+tr[da].r)>>1;
tr[da].lch=build(tr[da].lch,l,mids);
tr[da].rch=build(tr[da].rch,mids+1,r);
return da;
}
int ad(int da,int pre,int wz,int val){
if(!da){
da=++cnt;
tr[da].l=tr[pre].l;
tr[da].r=tr[pre].r;
}
tr[da].val+=val;
if(tr[da].l==tr[da].r){
return da;
}
rg int mids=(tr[da].l+tr[da].r)>>1;
if(wz<=mids) tr[da].lch=ad(tr[da].lch,tr[pre].lch,wz,val);
else tr[da].rch=ad(tr[da].rch,tr[pre].rch,wz,val);
return da;
}
void prexg(int wz,int val){
for(rg int i=wz;i<=n;i+=lb(i)){
rt[i]=ad(rt[i],rt[0],a[wz],val);
}
}
int cx(int l,int r,int k){
if(l==r) return l;
rg int mids=(l+r)>>1,nans=0;
for(rg int i=1;i<=cnt1;i++){
nans+=tr[tr[jl[1][i]].lch].val;
}
for(rg int i=1;i<=cnt0;i++){
nans-=tr[tr[jl[0][i]].lch].val;
}
if(k<=nans){
for(rg int i=1;i<=cnt0;i++){
jl[0][i]=tr[jl[0][i]].lch;
}
for(rg int i=1;i<=cnt1;i++){
jl[1][i]=tr[jl[1][i]].lch;
}
return cx(l,mids,k);
} else {
for(rg int i=1;i<=cnt0;i++){
jl[0][i]=tr[jl[0][i]].rch;
}
for(rg int i=1;i<=cnt1;i++){
jl[1][i]=tr[jl[1][i]].rch;
}
return cx(mids+1,r,k-nans);
}
}
int precx(int l,int r,int k){
memset(jl,0,sizeof(jl));
cnt0=cnt1=0;
for(rg int i=r;i>0;i-=lb(i)){
jl[1][++cnt1]=rt[i];
}
for(rg int i=l-1;i>0;i-=lb(i)){
jl[0][++cnt0]=rt[i];
}
return cx(1,tp,k);
}
int main(){
n=read(),m=read();
for(rg int i=1;i<=n;i++){
a[i]=read();
sta[++tp]=a[i];
}
rg int aa,bb,cc;
rg char ch;
for(rg int i=1;i<=m;i++){
scanf(" %c",&ch);
aa=read(),bb=read();
if(ch=='Q'){
cc=read();
b[i]=jie(ch,aa,bb,cc);
} else {
sta[++tp]=bb;
b[i]=jie(ch,aa,bb,0);
}
}
std::sort(sta+1,sta+1+tp);
tp=std::unique(sta+1,sta+1+tp)-sta-1;
for(rg int i=1;i<=n;i++){
a[i]=std::lower_bound(sta+1,sta+1+tp,a[i])-sta;
}
for(rg int i=1;i<=m;i++){
if(b[i].op=='C') b[i].ac2=std::lower_bound(sta+1,sta+1+tp,b[i].ac2)-sta;
}
rt[0]=build(1,1,tp);
for(rg int i=1;i<=n;i++){
prexg(i,1);
}
for(rg int i=1;i<=m;i++){
if(b[i].op=='Q') printf("%d
",sta[precx(b[i].ac1,b[i].ac2,b[i].ac3)]);
else {
prexg(b[i].ac1,-1);
a[b[i].ac1]=b[i].ac2;
prexg(b[i].ac1,1);
}
}
return 0;
}