描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1901
给出一个长度为n的数列A,有m次询问,询问分两种:1.修改某一位置的值;2.求区间[l,r]内的第k小的值.
1901: Zju2112 Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 6716 Solved: 2793
[Submit][Status][Discuss]
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。
Source
分析
对于只有第一种询问的问题: POJ_2104_Kth(主席树)
现在要求动态.我们思考这样一个问题:把求区间第k小的问题变成求区间和值的问题,这个好解决吧?对于静态的问题,我们使用前缀和即可解决,那么对于动态的呢?使用树状数组维护前缀和.那么现在把问题变回求区间第k小值的问题.对于静态的问题,我们还是使用前缀和的思想,不过这一次每个前缀和不再是代表[1,i]的和值,而是[1,i]的一棵线段树,然后找到区间左右断点,相减即可得到答案.者可以理解为"前缀和套线段树",并且我们使用可持久化的思想大大减小空间开销.那么对于动态的问题,我们还是使用树状数组的思想,不过这一次每个点不再代表[i-lowbit(i)+1,i]的和值,而是代表[i-lowbit[i]+1,i]的一棵线段树.问题就迎刃而解了.
注意:
1.这里的每一个点代表的主席树刚开始都是由root[i](=0)建立的,之后修改的时候已有的就不需要再建立了.由于主席树的空间需求不好估计(对于这样的问题,空间的上界是(n+m)(logn*logn),但实际上远远用不到),虽然也可以写成每次修改无论之前有没有都直接复制一份,但是在空间不确定的情况下,写成前一种不容易爆炸.
前一种:
#include <cstdio>
#include <algorithm>
using namespace std; const int maxn=+;
struct node{ int l,r,s; }t[maxn*];
struct qry{ int a,b,c; }q[maxn];
int n,m,cnt,tot,num;
int a[maxn],b[maxn<<],root[maxn],L[maxn],R[maxn]; inline int lowbit(int x){ return x&(-x); }
void update(int l,int r,int &pos,int d,int s){
if(!pos)t[++cnt]=t[pos], pos=cnt;
t[pos].s+=s;
if(l==r) return;
int mid=(l+r)/;
if(d<=mid) update(l,mid,t[pos].l,d,s);
else update(mid+,r,t[pos].r,d,s);
}
void change(int x,int d,int s){ for(;x<=n;x+=lowbit(x)) update(,num,root[x],d,s); }
int query(int l,int r,int k,int cl,int cr){
if(l==r) return l;
int suml=,sumr=;
for(int i=;i<=cl;i++) suml+=t[t[L[i]].l].s;
for(int i=;i<=cr;i++) sumr+=t[t[R[i]].l].s;
int s=sumr-suml,mid=(l+r)/;
if(k<=s){
for(int i=;i<=cl;i++) L[i]=t[L[i]].l;
for(int i=;i<=cr;i++) R[i]=t[R[i]].l;
return query(l,mid,k,cl,cr);
}
else{
for(int i=;i<=cl;i++) L[i]=t[L[i]].r;
for(int i=;i<=cr;i++) R[i]=t[R[i]].r;
return query(mid+,r,k-s,cl,cr);
}
}
int get_ans(int l,int r,int k){
int cl,cr;
for(cl=;l>;l-=lowbit(l)) L[++cl]=root[l];
for(cr=;r>;r-=lowbit(r)) R[++cr]=root[r];
return query(,num,k,cl,cr);
}
int main(){
scanf("%d%d",&n,&m);
char c;
for(int i=;i<=n;i++) scanf("%d",&a[i]), b[++tot]=a[i];
for(int i=;i<=m;i++){
for(c=getchar();c<'A'||c>'Z';c=getchar());
scanf("%d%d",&q[i].a,&q[i].b);
if(c=='Q') scanf("%d",&q[i].c);
else b[++tot]=q[i].b;
}
sort(b+,b++tot);
b[tot+]=0x7fffffff;
for(int i=;i<=tot;i++) if(b[i]!=b[i+]) b[++num]=b[i];
for(int i=;i<=n;i++) a[i]=lower_bound(b+,b++num,a[i])-b;
for(int i=;i<=n;i++) change(i,a[i],);
for(int i=;i<=m;i++){
if(q[i].c) printf("%d\n",b[get_ans(q[i].a-,q[i].b,q[i].c)]);
else{
change(q[i].a,a[q[i].a],-);
a[q[i].a]=lower_bound(b+,b++num,q[i].b)-b;
change(q[i].a,a[q[i].a],);
}
}
return ;
} 前一种
后一种:
#include <cstdio>
#include <algorithm>
using namespace std; const int maxn=+;
struct node{ int l,r,s; }t[maxn*];
struct qry{ int a,b,c; }q[maxn];
int n,m,cnt,tot,num;
int a[maxn],b[maxn<<],root[maxn],L[maxn],R[maxn]; inline int lowbit(int x){ return x&(-x); }
void update(int l,int r,int &pos,int d,int s){
t[++cnt]=t[pos]; t[cnt].s+=s; pos=cnt;
if(l==r) return;
int mid=(l+r)/;
if(d<=mid) update(l,mid,t[pos].l,d,s);
else update(mid+,r,t[pos].r,d,s);
}
void change(int x,int d,int s){ for(;x<=n;x+=lowbit(x)) update(,num,root[x],d,s); }
int query(int l,int r,int k,int cl,int cr){
if(l==r) return l;
int suml=,sumr=;
for(int i=;i<=cl;i++) suml+=t[t[L[i]].l].s;
for(int i=;i<=cr;i++) sumr+=t[t[R[i]].l].s;
int s=sumr-suml,mid=(l+r)/;
if(k<=s){
for(int i=;i<=cl;i++) L[i]=t[L[i]].l;
for(int i=;i<=cr;i++) R[i]=t[R[i]].l;
return query(l,mid,k,cl,cr);
}
else{
for(int i=;i<=cl;i++) L[i]=t[L[i]].r;
for(int i=;i<=cr;i++) R[i]=t[R[i]].r;
return query(mid+,r,k-s,cl,cr);
}
}
int get_ans(int l,int r,int k){
int cl,cr;
for(cl=;l>;l-=lowbit(l)) L[++cl]=root[l];
for(cr=;r>;r-=lowbit(r)) R[++cr]=root[r];
return query(,num,k,cl,cr);
}
int main(){
scanf("%d%d",&n,&m);
char c;
for(int i=;i<=n;i++) scanf("%d",&a[i]), b[++tot]=a[i];
for(int i=;i<=m;i++){
for(c=getchar();c<'A'||c>'Z';c=getchar());
scanf("%d%d",&q[i].a,&q[i].b);
if(c=='Q') scanf("%d",&q[i].c);
else b[++tot]=q[i].b;
}
sort(b+,b++tot);
b[tot+]=0x7fffffff;
for(int i=;i<=tot;i++) if(b[i]!=b[i+]) b[++num]=b[i];
for(int i=;i<=n;i++) a[i]=lower_bound(b+,b++num,a[i])-b;
for(int i=;i<=n;i++) change(i,a[i],);
for(int i=;i<=m;i++){
if(q[i].c) printf("%d\n",b[get_ans(q[i].a-,q[i].b,q[i].c)]);
else{
change(q[i].a,a[q[i].a],-);
a[q[i].a]=lower_bound(b+,b++num,q[i].b)-b;
change(q[i].a,a[q[i].a],);
}
}
return ;
}
p.s.这题可以用线段树套平衡树做(貌似树状数组套平衡树也是可以的?树状数组不太熟啊...)
线段树+Treap:
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std; const int maxn=+,oo=~0u>>;
int n,q;
int a[maxn];
char str[];
struct Treap{
struct node{
node* ch[];
int v,r,s,c;
node(int v,node* t):v(v){ ch[]=ch[]=t; r=rand(); s=c=; }
void push_up(){ s=ch[]->s+ch[]->s+c; }
}*root,*null;
Treap(){
null=new node(,NULL);
null->c=null->s=; null->r=oo;
root=null;
}
void rotate(node* &o,bool d){
node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o;
o->push_up(); k->push_up(); o=k;
}
void insert(node* &o,int x){
if(o==null) o=new node(x,null);
else{
if(x==o->v) o->s++, o->c++;
else{
bool d=x>o->v;
insert(o->ch[d],x);
if(o->ch[d]->r<o->r) rotate(o,!d);
o->push_up();
}
}
}
void remove(node* &o,int x){
if(o->v==x){
if(o->c>) o->c--, o->s--;
else{
if(o->ch[]!=null&&o->ch[]!=null){
bool d=o->ch[]->r<o->ch[]->r;
rotate(o,d); remove(o->ch[d],x); o->push_up();
}
else{
node* u=o;
o=o->ch[]==null?o->ch[]:o->ch[];
delete u;
}
}
}
else{
bool d=x>o->v;
remove(o->ch[d],x);
o->push_up();
}
}
int rank(int x){
int ret=;
for(node* t=root;t!=null;){
int s=t->ch[]->s+t->c;
if(x>t->v) ret+=s, t=t->ch[];
else t=t->ch[];
}
return ret;
}
int pre(int x){
int ret=-oo;
for(node* t=root;t!=null;){
if(t->v<x) ret=t->v, t=t->ch[];
else t=t->ch[];
}
return ret;
}
};
struct Segment_Tree{
Treap tree[maxn*];
void build_tree(int l,int r,int k){
for(int i=l;i<=r;i++) tree[k].insert(tree[k].root,a[i]);
if(l==r) return;
int mid=l+(r-l)/;
build_tree(l,mid,k<<); build_tree(mid+,r,k<<|);
}
int get_rank(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].rank(X);
int mid=l+(r-l)/;
if(y<=mid) return get_rank(l,mid,k<<,x,y,X);
else if(x>mid) return get_rank(mid+,r,k<<|,x,y,X);
else return get_rank(l,mid,k<<,x,mid,X)+get_rank(mid+,r,k<<|,mid+,y,X);
}
void change(int l,int r,int k,int id,int x){
tree[k].remove(tree[k].root,a[id]);
tree[k].insert(tree[k].root,x);
if(l==r) return;
int mid=l+(r-l)/;
if(id<=mid) change(l,mid,k<<,id,x);
else change(mid+,r,k<<|,id,x);
}
int get_pre(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].pre(X);
int mid=l+(r-l)/;
if(y<=mid) return get_pre(l,mid,k<<,x,y,X);
else if(x>mid) return get_pre(mid+,r,k<<|,x,y,X);
else return max(get_pre(l,mid,k<<,x,mid,X),get_pre(mid+,r,k<<|,mid+,y,X));
}
int get_kth(int x,int y,int k){
long long l=-oo,r=oo;
while(l<r){
int mid=(int)(l+(r-l)/);
int tmp=get_rank(,n,,x,y,mid)+;
if(tmp<=k) l=mid+;
else r=mid;
}
return get_pre(,n,,x,y,l);
}
}T; int main(){
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
T.build_tree(,n,);
for(int i=;i<=q;i++){
scanf("%s",str);
int l,r,k,id,x;
if(str[]=='Q'){
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",T.get_kth(l,r,k));
}
else{
scanf("%d%d",&id,&x);
T.change(,n,,id,x);
a[id]=x;
}
}
return ;
}