Loading...

权值线段树 学习笔记

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

不知道为啥我学了主席树却不会权值线段树qwq...

权值线段树就是将维护的区间改为了权值区间,类似的有值域分块等等,一般需要配合离散化

$1.$ 普通平衡树 洛谷$P3369$

这道题虽然说有$2\times 10^7$,但是无需离散化

#include <bits/stdc++.h>
using namespace std;
int sum[80000400];
#define pushup(o) sum[o]=sum[o<<1]+sum[o<<1|1]
void insert(int o,int lf,int rg,int x)
{
    if(lf==rg)
    {
        sum[o]++;
        return ;
    }
    int mid=(lf+rg)>>1;
    if(x<=mid)
    {
        insert(o<<1,lf,mid,x);
    }
    if(mid<x)
    {
        insert(o<<1|1,mid+1,rg,x);
    }
    pushup(o);
}
void del(int o,int lf,int rg,int x)
{
    if(lf==rg)
    {
        sum[o]--;
        return ;
    }
    int mid=(lf+rg)>>1;
    if(x<=mid)
    {
        del(o<<1,lf,mid,x);
    }
    if(mid<x)
    {
        del(o<<1|1,mid+1,rg,x);
    }
    pushup(o);
}
int myrank(int o,int lf,int rg,int x)
{
    if(lf==rg)
    {
        return 1;
    }
    if(rg<x)
    {
        return sum[o];
    }
    int mid=(lf+rg)>>1;
    if(x<=mid)
    {
        return myrank(o<<1,lf,mid,x);
    }
    if(mid<x)
    {
        return myrank(o<<1|1,mid+1,rg,x)+sum[o<<1];
    }
}
int mykth(int o,int lf,int rg,int x)
{
    if(lf==rg)
    {
        return lf-10000001;
    }
    int mid=(lf+rg)>>1;
    if(x<=sum[o<<1])
    {
        return mykth(o<<1,lf,mid,x);
    } 
    if(x>sum[o<<1])
    {
        return mykth(o<<1|1,mid+1,rg,x-sum[o<<1]);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)
        {
            x+=10000001;
            insert(1,1,20000003,x);
        }
        if(opt==2)
        {
            x+=10000001;
            del(1,1,20000003,x);
        }
        if(opt==3)
        {
            x+=10000001;
            printf("%d\n",myrank(1,1,20000003,x));
        }
        if(opt==4)
        {
            printf("%d\n",mykth(1,1,20000003,x));
        }
        if(opt==5)
        {
            printf("%d\n",mykth(1,1,20000003,myrank(1,1,20000003,x+10000001)-1));
        } 
        if(opt==6)
        {
            printf("%d\n",mykth(1,1,20000003,myrank(1,1,20000003,x+10000002)));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名