bzoj 1901: Zju2112 Dynamic Rankings -- 主席树，树状数组，哈希

1901: Zju2112 Dynamic Rankings

Time Limit: 10 Sec Memory Limit: 128 MB

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

HINT

如果查询第k大，我们直接用主席树就可以了，但是加上了修改操作，就需要再加上一维树状数组维护

这样就在每个lowbit修改就能维护出所有信息，查询同理。时间复杂度O(nlog²n)

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1000000007

#define ll long long

#define M 10000010

#define N 10010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m,v[N],A[N],B[N],K[N];

int hs[N<<],ji[N<<],tt,tot=;

int rt[N],sz[M],ls[M],rs[M],cnt;

char s[];

bool q[N];

int hsh(int x)

{

    int l=,r=tot,mid,mz;

    while(l<=r)

    {

        mid=l+r>>;

        if(hs[mid]<x) l=mid+;

        else r=mid-,mz=mid;

    }

    return mz;

}

void add(int lst,int l,int r,int &p,int x,int w)

{

    p=++cnt;

    sz[p]=sz[lst]+w;

    ls[p]=ls[lst];rs[p]=rs[lst];

    if(l==r) return;

    int mid=l+r>>;

    if(x<=mid) add(ls[lst],l,mid,ls[p],x,w);

    else add(rs[lst],mid+,r,rs[p],x,w);

}

int a,b,L[],R[];

int fd(int l,int r,int k)

{

    if(l==r) return l;

    int mid=l+r>>,sl=,sr=;

    for(int i=;i<=a;i++) sl+=sz[ls[L[i]]];

    for(int i=;i<=b;i++) sr+=sz[ls[R[i]]];

    if(sr-sl>=k)

    {

        for(int i=;i<=a;i++) L[i]=ls[L[i]];

        for(int i=;i<=b;i++) R[i]=ls[R[i]];

        return fd(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 fd(mid+,r,k-sr+sl);

    }

}

int main()

{

    tt=n=rd();m=rd();

    for(int i=;i<=n;i++) ji[i]=v[i]=rd();

    for(int i=;i<=m;i++)

    {

        scanf("%s",s);A[i]=rd();B[i]=rd();

        if(s[]=='Q') K[i]=rd();

        else ji[++tt]=B[i],q[i]=;

    }

    sort(ji+,ji+tt+);

    hs[]=ji[];

    for(int i=;i<=tt;i++)

        if(ji[i]!=ji[i-]) hs[++tot]=ji[i];

    for(int i=,tp;i<=n;i++)

    {

        tp=hsh(v[i]);

        for(int j=i;j<=n;j+=j&(-j))

            add(rt[j],,tot,rt[j],tp,);

    }

    for(int i=,tp;i<=m;i++)

    {

        if(q[i])

        {

            tp=hsh(v[A[i]]);

            for(int j=A[i];j<=n;j+=j&(-j))

                add(rt[j],,tot,rt[j],tp,-);

            tp=hsh(B[i]);

            for(int j=A[i];j<=n;j+=j&(-j))

                add(rt[j],,tot,rt[j],tp,);

            v[A[i]]=B[i];

        }

        else

        {

            a=b=;

            for(int j=A[i]-;j;j-=j&(-j)) L[++a]=rt[j];

            for(int j=B[i];j;j-=j&(-j)) R[++b]=rt[j];

            printf("%d\n",hs[fd(,tot,K[i])]);

        }

    }

    return ;

}

巴特西