动态求区间K大值（权值线段树）

时间：2021-12-15 06:04:37

我们知道我们可以通过主席树来维护静态区间第K大值。我们又知道主席树满足可加性，所以我们可以用树状数组来维护主席树，树状数组的每一个节点都可以开一颗主席树，然后一起做。

我们注意到树状数组的每一棵树都和前一颗树没有关系，so，并不需要可持久化，一个朴素的权值线段树就可以啦。

我们知道普通的线段树是刚开始就把所有的节点都开了，但我们发现并不需要，因为每个点里的操作并不是很多，很大一部分的节点是用不到的，那么我们就可以不开。用Ls 和 Rs 来记左右儿子的地址，随用随开即可。

#include<bits/stdc++.h>

#define N 100005

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

using namespace std;

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

int n,m,sz,totn,totx,toty,a[N],b[N<<],ca[N],cb[N],cc[N];

int xx[N],yy[N],rt[N],size[*N],ls[*N],rs[*N];

void ins(int l,int r,int x,int q,int v){

    size[x]+=v;

    if (l==r) return;

    if (q<=mid) { if (!ls[x]) ls[x]=++sz; ins(l,mid,ls[x],q,v);

    } else { if (!rs[x]) rs[x]=++sz; ins(mid+,r,rs[x],q,v);

    }

}

int query(int l,int r,int q){

    if(l==r)return l; int sum=;

    for(int i=;i<=totx;i++)sum-=size[ls[xx[i]]];

    for(int i=;i<=toty;i++)sum+=size[ls[yy[i]]];

    if(q<=sum){

        for(int i=;i<=totx;i++)xx[i]=ls[xx[i]];

        for(int i=;i<=toty;i++)yy[i]=ls[yy[i]];

        return query(l,mid,q);

    }

    else{

        for(int i=;i<=totx;i++)xx[i]=rs[xx[i]];

        for(int i=;i<=toty;i++)yy[i]=rs[yy[i]];

        return query(mid+,r,q-sum);

    }

}

void add(int x,int v){

    int k=lower_bound(b+,b+totn+,a[x])-b;

    for(int i=x;i<=n;i+=lowbit(i))ins(,totn,rt[i],k,v);

}

inline int read(){

    int f=,x=;char ch;

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

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

    return f*x;

}

int main(){char s[];

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

    for(int i=;i<=n;i++)a[i]=read(),b[++totn]=a[i];

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

        scanf("%s",s);ca[i]=read();cb[i]=read();

        if(s[]=='')cc[i]=read();else b[++totn]=cb[i];

    }

    sort(b+,b+totn+);

    totn=unique(b+,b+totn+)-b-;

    for (int i=;i<=n;i++) rt[i]=i; sz=n;

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

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

        if(cc[i]){

            totx=toty=;

            for(int j=ca[i]-;j;j-=lowbit(j))xx[++totx]=rt[j];

            for(int j=cb[i];j;j-=lowbit(j))yy[++toty]=rt[j];

            printf("%d\n",b[query(,totn,cc[i])]);

        }

        else{add(ca[i],-);a[ca[i]]=cb[i];add(ca[i],);}

    }

}

就酱紫。

相关文章