Loading...

动态主席树 学习笔记

check评论:0 条 remove_red_eye浏览量:94 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-10-30

小萌新$deco$终于学习了树状数组套主席树

其实也就是树状数组+主席树,不过因为每个树状数组的结点都存了很多棵主席树,所以我们每次先把要进行加减的主席树根节点全部提出来,然后再一起进行操作

修改的时候,对原数原位置$-1$,树状数组基本修改操作,然后修改后$+1$即可

注意要离散化qaq

还是非常简单的

例题

#include <bits/stdc++.h>
using namespace std;
int sum[15000010],l[15000010],r[15000010],a[200010],b[200010],t1[1000010],t2[1000010],t[200010];
#define lowbit(x) (x&(-x))
int pos[100010],num[100010];
int ql[100010],qr[100010],qk[100010];
int cnt=0,cnt1,cnt2,n,m,nt;
void update(int &now,int lf,int rg,int w,int x)
{
    if(!now)
    {
        now=++cnt;
    }
    sum[now]+=x;
    if(lf==rg)
    {
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        update(l[now],lf,mid,w,x);
    }
    else
    {
        update(r[now],mid+1,rg,w,x);
    }
}
int query(int u,int v,int k)
{
    if(u==v)
    {
        return u;
    }
    int x=0,mid=(u+v)>>1;
    for(int i=1;i<=cnt1;i++)
    {
        x-=sum[l[t1[i]]];
    }
    for(int i=1;i<=cnt2;i++)
    {
        x+=sum[l[t2[i]]];
    }
    if(x>=k)
    {
        for(int i=1;i<=cnt1;i++)
        {
            t1[i]=l[t1[i]];
        }
        for(int i=1;i<=cnt2;i++)
        {
            t2[i]=l[t2[i]];
        }
        return query(u,mid,k);
    }
    else
    {
        for(int i=1;i<=cnt1;i++)
        {
            t1[i]=r[t1[i]];
        }
        for(int i=1;i<=cnt2;i++)
        {
            t2[i]=r[t2[i]];
        }
        return query(mid+1,v,k-x);
    }
}
void add(int x,int w)
{
    for(int i=x;i<=nt;i+=lowbit(i))
    {
        update(t[i],1,nt,a[x],w);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    nt=n;
    for(int i=1;i<=m;i++)
    {
        char opt[4];
        int x,y,z;
        scanf("%s",opt);
        if(opt[0]=='Q')
        {
            scanf("%d%d%d",&ql[i],&qr[i],&qk[i]);
        }
        else
        {
            scanf("%d%d",&pos[i],&num[i]);
            b[++nt]=num[i];
        }
    }
    sort(b+1,b+nt+1);
    nt=unique(b+1,b+nt+1)-b-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+nt+1,a[i])-b;
        add(i,1);
    }
    for(int i=1;i<=m;i++)
    {
        if(pos[i]==0)
        {
            cnt1=cnt2=0;
            for(int x=ql[i]-1;x;x-=lowbit(x))
            {
                t1[++cnt1]=t[x];
            }
            for(int x=qr[i];x;x-=lowbit(x))
            {
                t2[++cnt2]=t[x];
            }
            cout<<b[query(1,nt,qk[i])]<<"\n";
        }
        else
        {
            num[i]=lower_bound(b+1,b+nt+1,num[i])-b;
            add(pos[i],-1);
            a[pos[i]]=num[i];
            add(pos[i],1); 
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名