【bzoj1901】Zju2112 Dynamic Rankings

2015.05.20 10:05 Wed | 29次阅读 | 旧日oi | 固定链接 | 源码

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

Sample Output

3
6

HINT

20%的数据中,m,n≤100; 40%的数据中,m,n≤1000; 100%的数据中,m,n≤10000。

题解

求带修改的区间第k小。
做法是主席树套树状数组,正常写的主席树是类似前缀和的形式,root[i]这颗树存的是1~i这些元素。而套上了树状数组之后,root[i]存的是想树状数组中存的那些元素,这样每次修改我们只修改log(n)颗树,查询也是在log(n)颗树中查询就好了。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 20005
using namespace std;
int n,m,cnt,t1,t2,siz;
int L[N],R[N],root[N],a[N],num[N],rank[N],p[N],c[N];
int ls[N*200],rs[N*200],sum[N*200];
struct que{
    int l,r,k;
}q[N];
char s[2];
int lowbit(int x)
{
    return x&(-x); 
}
void update(int t,int l,int r,int &x,int pos,int v)
{
    sum[x=++siz]=sum[t]+v;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) rs[x]=rs[t],update(ls[t],l,mid,ls[x],pos,v);
    else ls[x]=ls[t],update(rs[t],mid+1,r,rs[x],pos,v); 
}
int query(int l,int r,int k)
{
    if(l==r) return l;
    int suml=0,sumr=0;
    for(int i=1;i<=t1;i++) suml+=sum[ls[L[i]]];
    for(int i=1;i<=t2;i++) sumr+=sum[ls[R[i]]];
    int mid=(l+r)>>1;
    if(sumr-suml>=k)
    {
        for(int i=1;i<=t1;i++) L[i]=ls[L[i]];
        for(int i=1;i<=t2;i++) R[i]=ls[R[i]];
        return query(l,mid,k);
    }
    else
    {
        for(int i=1;i<=t1;i++) L[i]=rs[L[i]];
        for(int i=1;i<=t2;i++) R[i]=rs[R[i]];
        return query(mid+1,r,k-(sumr-suml));
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[++cnt]=a[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='Q') scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        else scanf("%d%d",&p[i],&c[i]),num[++cnt]=c[i];
    }
    sort(num+1,num+cnt+1);
    int top=unique(num+1,num+cnt+1)-num-1;
    for(int i=1;i<=n;i++) 
    {
        int t=lower_bound(num+1,num+top+1,a[i])-num;
        rank[t]=a[i];
        for(int j=i;j<=n;j+=lowbit(j))
        update(root[j],1,top,root[j],t,1);
    }
    for(int i=1;i<=m;i++)
    {
        if(q[i].k) 
        {
            t1=t2=0;q[i].l--;int x=q[i].l,y=q[i].r;
            for(;x;x-=lowbit(x)) L[++t1]=root[x];
            for(;y;y-=lowbit(y)) R[++t2]=root[y];
            printf("%d\n",rank[query(1,top,q[i].k)]);
        }
        else
        {
            int t=lower_bound(num+1,num+top+1,a[p[i]])-num;
            for(int j=p[i];j<=n;j+=lowbit(j)) update(root[j],1,top,root[j],t,-1);
            a[p[i]]=c[i];
            t=lower_bound(num+1,num+top+1,a[p[i]])-num;rank[t]=a[p[i]];
            for(int j=p[i];j<=n;j+=lowbit(j)) update(root[j],1,top,root[j],t,1);
        }
    }
}```