Description
给定一个含有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。
Input
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Output
Sample Input
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
6
HINT
20%的数据中，m,n≤100; 40%的数据中，m,n≤1000; 100%的数据中，m,n≤10000。
树套树
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=,inf=;
struct tree{int lch,rch,num,sz,w,rnd;}tr[N];
int a[],n,m,sz,root[*];
void updata(int x){
int l=tr[x].lch,r=tr[x].rch;
tr[x].sz=tr[l].sz+tr[r].sz+tr[x].w;
} void lturn(int &k)
{int t=tr[k].rch;tr[k].rch=tr[t].lch;tr[t].lch=k;updata(k);updata(t);k=t;}
void rturn(int &k)
{int t=tr[k].lch;tr[k].lch=tr[t].rch;tr[t].rch=k;updata(k);updata(t);k=t;}
void ins(int &k,int x){
if(!k){
k=++sz;tr[k].rnd=rand();tr[k].sz=;tr[k].num=x;tr[k].w=;return;
}
if(tr[k].num==x) tr[k].w++;
else if(tr[k].num>x) {
ins(tr[k].lch,x);
if(tr[k].rnd>tr[tr[k].lch].rnd) rturn(k);
}else{
ins(tr[k].rch,x);
if(tr[k].rnd>tr[tr[k].rch].rnd) lturn(k);
}
updata(k);
} void insert(int k,int l,int r,int x,int y){
if(l<=y&&r>=y) ins(root[k],x);
if(l==r) return;
int mid=(l+r)>>;
if(y>mid) insert(k<<|,mid+,r,x,y);
else insert(k<<,l,mid,x,y);
} int find(int k,int x){
if(!k) return ;
int l=tr[k].lch,r=tr[k].rch;
if(tr[k].num>x) return find(l,x);
else if(tr[k].num<x) return find(r,x)+tr[l].sz+tr[k].w;
else return tr[l].sz;
} int get_rank(int k,int l,int r,int L,int R,int x){
int mid=(l+r)>>;
if(l==L&&r==R) return find(root[k],x);
if(R<=mid) return get_rank(k<<,l,mid,L,R,x);
else if(L>mid) return get_rank(k<<|,mid+,r,L,R,x);
else return get_rank(k<<,l,mid,L,mid,x)+get_rank(k<<|,mid+,r,mid+,R,x);
} int ask(int x,int y,int rk){
int l=,r=inf,mid=(l+r)>>,ans=;
while(l<=r){
mid=(l+r)>>;
int k=get_rank(,,n,x,y,mid);
if(k<=rk) ans=mid,l=mid+;
else r=mid-;
}
return ans;
} void del(int &k,int p){
if(tr[k].num==p){
if(tr[k].w>) tr[k].w--,tr[k].sz--;
else{
if(tr[k].lch*tr[k].rch==) k=tr[k].lch+tr[k].rch;
else if(tr[tr[k].lch].rnd<tr[tr[k].rch].rnd) rturn(k),del(k,p);
else lturn(k),del(k,p);
}
}
else{
tr[k].sz--;
if(tr[k].num>p) del(tr[k].lch,p);else del(tr[k].rch,p);
}
} void make(int &rt,int p,int t){
ins(rt,t);
del(rt,p);
} void change(int k,int l,int r,int x,int p,int t){
if(l<=x&&r>=x) make(root[k],p,t);
if(l==r) return;
int mid=(l+r)>>;
if(x<=mid) change(k<<,l,mid,x,p,t);
else change(k<<|,mid+,r,x,p,t);
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
insert(,,n,a[i],i);
}
char s[];
for(int i=;i<=m;i++){
scanf("%s",s);
if(s[]=='Q') {
int l,r,rk;
scanf("%d%d%d",&l,&r,&rk);
printf("%d\n",ask(l,r,rk-));
}else{
int x,t;
scanf("%d%d",&x,&t);
change(,,n,x,a[x],t);
a[x]=t;
}
}
}
树状数组+主席树
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2200001
using namespace std;
int n,m,tot,top,cnt;
int v[],num[];
int A[],B[],X[],root[],K[];
int sz[N],ls[N],rs[N];
int L[],R[],a,b;
int lowbit(int x){return x&(-x);}
void updata(int last,int l,int r,int &k,int x,int add){
k=++cnt;
int mid=(l+r)>>;
sz[k]=sz[last]+add;ls[k]=ls[last];rs[k]=rs[last];
if(l==r) return;
if(x<=mid) updata(ls[last],l,mid,ls[k],x,add);
else updata(rs[last],mid+,r,rs[k],x,add);
} int query(int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>;
int suml=,sumr=;
for(int i=;i<=a;i++)suml+=sz[ls[L[i]]];
for(int i=;i<=b;i++)sumr+=sz[ls[R[i]]];
if(sumr-suml>=k){
for(int i=;i<=a;i++) L[i]=ls[L[i]];
for(int i=;i<=b;i++) R[i]=ls[R[i]];
return query(l,mid,k);
}else{
for(int i=;i<=a;i++) L[i]=rs[L[i]];
for(int i=;i<=b;i++) R[i]=rs[R[i]];
return query(mid+,r,k-(sumr-suml));
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&v[i]);
num[++top]=v[i];
}
char opt[];
for(int i=;i<=m;i++){
scanf("%s%d%d",opt,&A[i],&B[i]);
if(opt[]=='Q') scanf("%d",&X[i]),K[i]=;
else num[++top]=B[i];
}
sort(num+,num+top+);
tot=unique(num+,num+top+)-num-;
for(int i=;i<=n;i++){
int t=lower_bound(num+,num+tot+,v[i])-num;
for(int j=i;j<=n;j+=lowbit(j))
updata(root[j],,tot,root[j],t,);
}
for(int i=;i<=m;i++){
if(K[i]){
a=,b=;A[i]--;
for(int j=A[i];j>=;j-=lowbit(j)) L[++a]=root[j];
for(int j=B[i];j>=;j-=lowbit(j)) R[++b]=root[j];
printf("%d\n",num[query(,tot,X[i])]);
}else{
int t=lower_bound(num+,num+tot+,v[A[i]])-num;
for(int j=A[i];j<=n;j+=lowbit(j))
updata(root[j],,tot,root[j],t,-);
v[A[i]]=B[i];
t=lower_bound(num+,num+tot+,v[A[i]])-num;
for(int j=A[i];j<=n;j+=lowbit(j))
updata(root[j],,tot,root[j],t,);
}
}
}
整体二分
#include<cstdio>
const int inf=;
struct node{int flag,x,y,no,rk,cur;}p[],p1[],p2[];
int n,m,a[],cnt,sum,ans[],w[],tmp[],num; void add(int x,int y){
for(int i=x;i<=n;i+=(i&(-i))) w[i]+=y;
} int query(int x){
int ans=;
for (int i=x;i>;i-=(i&(-i))) ans+=w[i];
return ans;
} void divid(int h,int t,int l,int r){
if(h>t) return;
if(l==r) {for(int i=h;i<=t;i++)
ans[p[i].no]=l;return;}
int mid=(l+r)>>;
for(int i=h;i<=t;i++){
if(p[i].flag==&&p[i].y<=mid) add(p[i].x,);
else if(p[i].flag==&&p[i].y<=mid) add(p[i].x,-);
else if(p[i].flag==)tmp[i]=query(p[i].y)-query(p[i].x-);
}
for(int i=h;i<=t;i++){
if(p[i].flag==&&p[i].y<=mid) add(p[i].x,-);
else if(p[i].flag==&&p[i].y<=mid) add(p[i].x,);
}
int l1=,l2=;
for(int i=h;i<=t;i++){
if(p[i].flag==){
if(tmp[i]+p[i].cur>p[i].rk-) p1[++l1]=p[i];
else p[i].cur+=tmp[i],p2[++l2]=p[i];
}
else {
if(p[i].y<=mid) p1[++l1]=p[i];else p2[++l2]=p[i];
}
}
for(int i=h;i<=l1+h-;i++) p[i]=p1[i-h+];
for(int i=l1+h;i<=t;i++) p[i]=p2[i-l1-h+];
divid(h,l1+h-,l,mid);
divid(l1+h,t,mid+,r);
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
p[++cnt].flag=;p[cnt].x=i;p[cnt].y=a[i];
}
for(int i=;i<=m;i++){
char opt[];int x,y,k;
scanf("%s%d%d",opt,&x,&y);
if(opt[]=='Q'){
scanf("%d",&k);
p[++cnt].x=x,p[cnt].y=y;p[cnt].flag=;p[cnt].no=++num;
p[cnt].rk=k;
}else{
p[++cnt].x=x;p[cnt].y=a[x];p[cnt].flag=;
a[x]=y;
p[++cnt].x=x;p[cnt].y=a[x];p[cnt].flag=;
}
}
divid(,cnt,,inf);
for(int i=;i<=num;i++) printf("%d\n",ans[i]);
}
这就是时间差距。。。