bzoj1901Zju2112 Dynamic Rankings

bzoj1901Zju2112 Dynamic Rankings

​​ 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继续回答上面的问题。 Input 第一行有两个正整数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 Output 对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input 5 3

3 2 1 4 7

Q 1 4 3

C 2 6

Q 2 5 3

Sample Output 3

6

这次是带修改的区间查询 针对每个点我去建立一个权值线段树 然后添加的时候 针对线段树建立树状数组 然后主席树的用处在于假如我需要针对这个点的权值进行修改 那么我需要重新建一个树然后把之前的标记除了要修改的点 全部移动过去 然后再add 重新建一棵树 利用树状数组快速求前缀和 时间复杂度是n*(log(n))^2 用线段树统计 区间内到底有多少个树 然后就可以log的复杂度求区间第k 小

#include#include#define N 11000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int l,r,k;}qr[N];struct node1{ int left,right,v;}tree[N*400];int n,m,nn,b[N<<1],a[N],ss[N],ll[N],rr[N],ln,rn,num,root[N<<1],a1[N<<1];inline void insert1(int &x,int l,int r,int p,int v){ tree[++num]=tree[x];x=num;tree[x].v+=v; if (l==r) return;int mid=l+r>>1; if (p<=mid) insert1(tree[x].left,l,mid,p,v);else insert1(tree[x].right,mid+1,r,p,v); }inline void add(int x,int v){for (int i=x;i<=n;i+=i&(-i)) insert1(root[i],1,nn,a1[x],v);}int query(int l,int r,int k){ if (l==r) return l;int mid=l+r>>1,size=0; for (int i=1;i<=ln;++i) size-=tree[tree[ll[i]].left].v; for (int i=1;i<=rn;++i) size+=tree[tree[rr[i]].left].v; if (k<=size){ for (int i=1;i<=ln;++i) ll[i]=tree[ll[i]].left;for (int i=1;i<=rn;++i) rr[i]=tree[rr[i]].left;return query(l,mid,k); }else{ for (int i=1;i<=ln;++i) ll[i]=tree[ll[i]].right;for (int i=1;i<=rn;++i) rr[i]=tree[rr[i]].right;return query(mid+1,r,k-size); }}int main(){ freopen("bzoj1901.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i) a[i]=read(),b[i]=a[i];int cnt=n; for (int i=1;i<=m;++i){char ch=gc(); while(ch!='Q'&&ch!='C') ch=gc();qr[i].l=read();qr[i].r=read(); if (ch=='Q') qr[i].k=read();else b[++cnt]=qr[i].r; }sort(b+1,b+cnt+1);nn=unique(b+1,b+cnt+1)-b-1; for (int i=1;i<=n;++i) a1[i]=lower_bound(b+1,b+nn+1,a[i])-b,add(i,1); for (int i=1;i<=m;++i){ if (qr[i].k){ ln=rn=0;for (int j=qr[i].l-1;j;j-=j&(-j)) ll[++ln]=root[j]; for (int j=qr[i].r;j;j-=j&(-j)) rr[++rn]=root[j];printf("%d\n",b[query(1,nn,qr[i].k)]); }else{ add(qr[i].l,-1);a1[qr[i].l]=lower_bound(b+1,b+nn+1,qr[i].r)-b;add(qr[i].l,1); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。