AC日记——Dynamic Ranking 洛谷 P2617

Dynamic Ranking

思路；

　　可持久化树状数组；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 10005

#define maxtot maxn*600

struct QueryType {

    int l,r,k;

    char op[];

};

struct QueryType qu[maxn];

int n,m,ai[maxn],bi[maxn<<],root[maxn];

int posl[],numl,posr[],numr,lc[maxtot];

int rc[maxtot],dis[maxtot],tot,cnt,size;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline int lowbit(int x)

{

    return x&(-x);

}

inline void add(int &now,int l,int r,int to,int x)

{

    if(!now) now=++tot;dis[now]+=x;

    if(l==r) return;int mid=l+r>>;

    if(to<=mid) add(lc[now],l,mid,to,x);

    else add(rc[now],mid+,r,to,x);

}

inline void tree_add(int x,int to,int di)

{

    while(x<=n)

    {

        add(root[x],,size,to,di);

        x+=lowbit(x);

    }

}

inline void pre(int l,int r)

{

    l--,numl=,numr=;

    while(r) posr[++numr]=root[r],r-=lowbit(r);

    while(l) posl[++numl]=root[l],l-=lowbit(l);

}

inline int query(int l,int r,int k)

{

    if(l==r) return bi[l];

    int di=,mid=l+r>>;

    for(int i=;i<=numr;i++) di+=dis[lc[posr[i]]];

    for(int i=;i<=numl;i++) di-=dis[lc[posl[i]]];

    if(k<=di)

    {

        for(int i=;i<=numr;i++) posr[i]=lc[posr[i]];

        for(int i=;i<=numl;i++) posl[i]=lc[posl[i]];

        return query(l,mid,k);

    }

    else

    {

        for(int i=;i<=numr;i++) posr[i]=rc[posr[i]];

        for(int i=;i<=numl;i++) posl[i]=rc[posl[i]];

        return query(mid+,r,k-di);

    }

}

int main()

{

    in(n),in(m);

    for(int i=;i<=n;i++) in(ai[i]),bi[++cnt]=ai[i];

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

    {

        scanf("%s",qu[i].op),in(qu[i].l),in(qu[i].r);

        if(qu[i].op[]=='Q') in(qu[i].k);

        else bi[++cnt]=qu[i].r;

    }

    sort(bi+,bi+cnt+),size=unique(bi+,bi+cnt+)-bi-;

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

    {

        ai[i]=lower_bound(bi+,bi+size+,ai[i])-bi;

        tree_add(i,ai[i],);

    }

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

    {

        if(qu[i].op[]=='Q')

        {

            pre(qu[i].l,qu[i].r);

            printf("%d\n",query(,size,qu[i].k));

        }

        else

        {

            qu[i].r=lower_bound(bi+,bi+size+,qu[i].r)-bi;

            tree_add(qu[i].l,ai[qu[i].l],-);

            ai[qu[i].l]=qu[i].r;

            tree_add(qu[i].l,qu[i].r,);

        }

    }

    return ;

}