带修主席树

迈不过友情╰ 2024-04-18 16:27 9阅读 0赞

板子大概这个样子，没有交，今天有点累，不想debug了

#include<bits/stdc++.h>
    using namespace std;
    const int M = 1e5+50;
    struct Node{int l,r,sum;}t[M*400];
    struct QUE{int id,op,i,j,k;}q[M];
    int n,m,a[M],b[M<<1],tot,cnt,rt[M];
    char op[6];
    void add(int &now,int l,int r,int pos,int v){
        if(!now)now=++cnt;
        t[now].sum+=v;
        if(l==r)return ;
        int mid=(l+r)>>1;
        if(pos<=mid)add(t[now].l,l,mid,pos,v);
        if(mid<r)add(t[now].r,mid+1,r,pos,v);
    }
    void Add(int x,int pos,int v){
        while(x<=n){
            add(rt[x],1,tot,pos,v);
            x+=(x&-x);
        }
    }
    int xx[35],yy[35];
    void slove(int x,int y,int k){
        x--;
        int t1=0,t2=0;
        swap(x,y);
        int t1=0,t2=0;
        for(int i=x;i>=1;i-=(i&-x))xx[++t1]=rt[i];
        for(int i=y;i>=1;i-=(i&-x))yy[++t1]=rt[i];
        int l=1,r=tot,tem=0;
        while(l<r){
            int tem=0;
            for(int i=1;i<=t1;i++)tem+=t[t[xx[i]].l].sum;
            for(int i=1;i<=t2;i++)tem-=t[t[yy[i]].l].sum;
            if(k<=tem){
                for(int i=1;i<=t1;i++)tem+=t[xx[i]].l;
                for(int i=1;i<=t2;i++)tem-=t[yy[i]].l;
                r=(l+r)/2;
            }else{
                for(int i=1;i<=t1;i++)tem+=t[xx[i]].r;
                for(int i=1;i<=t2;i++)tem-=t[yy[i]].r;
                k-=tem;l=(l+r)/2+1;
            }
        }
        printf("%d\n",l);
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",a+i),b[++tot]=a[i];
        for(int i=1;i<=m;i++){
            scanf("%s",op);
            q[i].id=i;
            if(op[0]=='Q')q[i].op=1,scanf("%d%d%d",&q[i].i,&q[i].j,&q[i].k);
            else q[i].op=2,scanf("%d%d",&q[i].i,&q[i].k);
            b[++tot]=q[i].k;
        }
        sort(b+1,b+tot+1);
        cnt=1;for(int i=2;i<=tot;i++)if(b[i]!=b[i-1])b[++cnt]=b[i];tot=cnt;cnt=0;
    
        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot+1,a[i]);
        for(int i=1;i<=m;i++)q[i].k=lower_bound(b+1,b+tot+1,q[i].k);
    
        for(int i=1;i<=n;i++)Add(i,a[i],1);//直接插入主席树，
    
        for(int i=1;i<=m;i++){
            if(q[i].op==1){
                int res=query(q[i].j,);
            }else{
                slove(q[i].i,q[i].j,q[i].k);
            }
        }
        return 0;
    }