【BZOJ1901】【Luogu2617】Dynamic Ranking（主席树，树状数组）

题面

神TM BZOJ权限题

Luogu真良心

题解

如果不考虑修改

很容易的主席树区间第K大

考虑修改

那么修改操作复杂度\(O(nlogn)\)

因此，将区间的和利用树状数组来维护

修改复杂度降为\(O(log^2n)\)

虽然查询的复杂度升为\(O(log^2n)\)

但是整体复杂度变为\(O(mlog^2n)\)

于是就愉快的AC了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 20005

#define lson t[now].ls

#define rson t[now].rs

#define mid ((l+r)>>1)

#define Q q

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Node

{

    int v;

    int ls,rs;

}t[MAX<<9];

int tot;

int S[MAX],sum,a[MAX],n,m;

int rt[MAX],cnt0,cnt1;

int tmp[3][MAX];

struct OPT

{

    bool opt;

    int l,r,k;

    int pos,t;

}Q[MAX];

inline int lowbit(int x){return x&(-x);}

void Modify(int &now,int l,int r,int pos,int val)

{

    if(!now)now=++tot;

    t[now].v+=val;

    if(l==r)return;

    if(pos<=mid)Modify(lson,l,mid,pos,val);

    else Modify(rson,mid+1,r,pos,val);

}

void PreModify(int x,int val)

{

    int k=lower_bound(&S[1],&S[sum+1],a[x])-S;

    while(x<=n)

    {

        Modify(rt[x],1,sum,k,val);

        x+=lowbit(x);

    }

}

int Query(int l,int r,int k)

{

    if(l==r)return l;

    int s=0;

    for(int i=1;i<=cnt1;++i)s+=t[t[tmp[1][i]].ls].v;

    for(int i=1;i<=cnt0;++i)s-=t[t[tmp[0][i]].ls].v;

    if(k<=s)

    {

        for(int i=1;i<=cnt1;++i)tmp[1][i]=t[tmp[1][i]].ls;

        for(int i=1;i<=cnt0;++i)tmp[0][i]=t[tmp[0][i]].ls;

        return Query(l,mid,k);

    }

    else

    {

        for(int i=1;i<=cnt1;++i)tmp[1][i]=t[tmp[1][i]].rs;

        for(int i=1;i<=cnt0;++i)tmp[0][i]=t[tmp[0][i]].rs;

        return Query(mid+1,r,k-s);

    }

}

int PreQuery(int l,int r,int k)

{

    cnt0=cnt1=0;l--;

    while(r)tmp[1][++cnt1]=rt[r],r-=lowbit(r);

    while(l)tmp[0][++cnt0]=rt[l],l-=lowbit(l);

    return Query(1,sum,k);

}

char opt[3];

int main()

{

    n=read();m=read();

    for(int i=1;i<=n;++i)S[++sum]=a[i]=read();

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

    {

        scanf("%s",opt);

        q[i].opt=opt[0]=='Q';

        if(q[i].opt)q[i].l=read(),q[i].r=read(),q[i].k=read();

        else q[i].pos=read(),q[i].t=S[++sum]=read();

    }

    sort(&S[1],&S[sum+1]);

    sum=unique(&S[1],&S[sum+1])-S-1;

    for(int i=1;i<=n;++i)PreModify(i,1);

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

    {

        if(q[i].opt)

        {

            printf("%d\n",S[PreQuery(Q[i].l,Q[i].r,Q[i].k)]);

        }

        else

        {

            PreModify(Q[i].pos,-1);

            a[Q[i].pos]=Q[i].t;

            PreModify(Q[i].pos,1);

        }

    }

    return 0;

}