P2617 Dynamic Rankings

题目描述

给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\)，需要支持两种操作：

• Q l r k 表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数
• C x y 表示将 \(a_x\) 改为 \(y\)

【数据范围】

对于 \(100\%\) 的数据，\(1\le n,m \le 10^5\)，\(1 \le l \le r \le n\)，\(1 \le k \le r-l+1\)，\(1\le x \le n\)，\(0 \le a_i,y \le 10^9\)。

Solution:

生套生 模板题，用树状数组维护主席树的前缀和。

首先我们都知道主席树的本质其实是前缀和，如果我们要修改一个点的点权，那么就会牵扯到至多 \(O(n)\) 颗树（它的后继）。这样我们就会十分难受，怎么办呢？

还记得当年在学前缀和时老师同时教了另一个东西: 树状数组。我们在建树时，可以不按照线性前缀和，而在树状数组上建树，这样我们在单点修改时只用修改 \(log_{2}n\) 个点就好了，这样的时间复杂度就是

#include<bits/stdc++.h>
const int N=1e5+5;
const int inf=1e9;
using namespace std;
inline int lowbit(int x){return x&-x;}
int n,m;
int a[N];
struct Segment_Tree{
    struct Tree{
        int ls,rs,cnt;
    }t[N*400];
    int cnt,rt[N];
    void insert(int &x,int l,int r,int pos,int k)
    {
        t[x=(x ? x : ++cnt)].cnt+=k;
        if(l==r)return ;
        int mid=l+r>>1;
        if(pos<=mid)insert(t[x].ls,l,mid,pos,k);
        if(mid<pos) insert(t[x].rs,mid+1,r,pos,k);
    }
    void update(int x,int val,int k)
    {
        for(int u=x;u<=n;u+=lowbit(u))insert(rt[u],0,inf,val,k);
    }
    int A[N],B[N];
    int query(int x,int y,int k)
    {
        A[0]=B[0]=0;
        for(int u=x-1;u;u-=lowbit(u))A[++A[0]]=rt[u];
        for(int u=y;u;u-=lowbit(u))B[++B[0]]=rt[u];
        int l=0,r=inf,ans=0,mid=0,tmp;
        while(l<r)
        {
            mid=l+r>>1;
            tmp=0;
            for(int i=1;i<=A[0];i++)tmp-=t[t[A[i]].rs].cnt;
            for(int i=1;i<=B[0];i++)tmp+=t[t[B[i]].rs].cnt;
            if(tmp>=k)
            {
                for(int i=1;i<=A[0];i++)A[i]=t[A[i]].rs;
                for(int i=1;i<=B[0];i++)B[i]=t[B[i]].rs;
                l=ans=mid+1;
            }
            else
            {
                for(int i=1;i<=A[0];i++)A[i]=t[A[i]].ls;
                for(int i=1;i<=B[0];i++)B[i]=t[B[i]].ls;
                r=mid;k-=tmp;
            }
        }
        return ans;
    }
}T;
char c[10];
void work()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        T.update(i,a[i],1);
    }
    for(int i=1,x,y,k;i<=m;i++)
    {
        scanf("%s",c);
        scanf("%d%d",&x,&y);
        if(c[0]=='C')
        {
            T.update(x,a[x],-1);
            a[x]=y;
            T.update(x,a[x],1);
        }
        else
        {
            scanf("%d",&k);
            k=y-x+1-k+1;
            int ans=T.query(x,y,k);
            printf("%d\n",ans);
        }
    }
}
int main()
{
    //freopen("Dynamic Rankings.in","r",stdin);freopen("Dynamic Rankings.out","w",stdout);
    work();
    return 0;
}