zoj2112&&bzoj1901

题解：

可修改的主席树

一开始，我就按照最暴力的方法，空间nlognlogn

然后zju上面过不了，bzoj没有权限号

然后，参考了往上的论文，发现可以把初始的主席树先建好

然后，每次只需要维护修改的就可以了

而且修改的内容只有2个数字

可以快那么一些

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ls(x) t[x].lc

#define rs(x) t[x].rc

typedef long long ll;

const int N=;

int read()

{

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

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

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

    return x*f;

}

int q1[N],t1,q2[N],t2,sz=,root[N],rt[N],n,Q,m,a[N],mp[N*],i,j,k;

char s[];

struct question

{

    char s[];

    int i,j,k,x,d;

}q[N];

struct node

{

    int lc,rc,w;

}t[N*];

int Bin(int v)

{

    int l=,r=m;

    while (l<=r)

     {

        int mid=(l+r)>>;

        if(mp[mid]==v) return mid;

        if(mp[mid]>v) r=mid-;

        else l=mid+;

     }

    return -;

}

void ins(int &x,int l,int r,int num,int v)

{

    t[++sz]=t[x];x=sz;

    t[x].w+=v;

    if(l==r) return;

    int mid=(l+r)>>;

    if (num<=mid) ins(t[x].lc,l,mid,num,v);

    else ins(t[x].rc,mid+,r,num,v);

}

void add(int p,int v)

{

    int xx=Bin(a[p]);

    for (int i=p;i<=n;i+=i&-i) ins(root[i],,m,xx,v);

}

int cal()

{

    int sum1=,sum2=;

    for (int i=;i<=t1;i++) sum1+=t[ls(q1[i])].w;

    for (int i=;i<=t2;i++) sum2+=t[ls(q2[i])].w;

    return sum2-sum1;

}

int query(int ql,int qr,int k)

{

    int l=,r=m;t1=t2=;

    for (int i=ql-;i;i-=i&-i) q1[++t1]=root[i];

    for (int i=qr;i;i-=i&-i) q2[++t2]=root[i];

    ql--;

    ql=rt[ql];qr=rt[qr];

    while (l<r)

     {

        int lsize=cal()+t[ls(qr)].w-t[ls(ql)].w,mid=(l+r)>>;

        if (k<=lsize)

         {

            for (int i=;i<=t1;i++) q1[i]=t[q1[i]].lc;

            for (int i=;i<=t2;i++) q2[i]=t[q2[i]].lc;

            ql=ls(ql);qr=ls(qr);

            r=mid;

         }

        else

         {

            for (int i=;i<=t1;i++) q1[i]=t[q1[i]].rc;

            for (int i=;i<=t2;i++) q2[i]=t[q2[i]].rc;

            ql=rs(ql);qr=rs(qr);

            l=mid+;k-=lsize;

         }

     }

    return l;

}

int main()

{

    int T=read();

    while (T--)

     {

         m=sz=;

         memset(q,,sizeof q);

         memset(t,,sizeof t);

         memset(rt,,sizeof rt);

         memset(root,,sizeof root);

        n=read();Q=read();

        for (int i=;i<=n;i++)a[i]=mp[++m]=read();

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

         {

            scanf("%s",q[i].s);

            if (q[i].s[]=='Q') q[i].i=read(),q[i].j=read(),q[i].k=read();

            else q[i].x=read(),q[i].d=mp[++m]=read();

         }

        sort(mp+,mp++m);

        int p=;

        for (int i=;i<=m;i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];

        m=p;

        for (int i=;i<=n;i++) rt[i]=rt[i-],ins(rt[i],,m,Bin(a[i]),);

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

         {

            if(q[i].s[]=='Q')

             printf("%d\n",mp[query(q[i].i,q[i].j,q[i].k)]);

            else

             {

                add(q[i].x,-);

                a[q[i].x]=q[i].d;

                add(q[i].x,);

             }

         }

     }

    return ;

}