首页 > 其他分享 >《权值线段树详解》——代码仓库

《权值线段树详解》——代码仓库

时间：2023-01-31 17:13:34浏览次数：46  
标签：return int 线段 mid cin 详解 ls 权值 define

P3369 【模板】普通平衡树

#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e5+5;
const int MOV = 1e7;

struct node{
    int v,l,r;
} t[N<<4];
int tot,root;

inline void newnode(int &i){
    if(!i) i=(++tot);
}

void update(int p,int v,int &i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r){
        if(t[i].v<0) t[i].v=0;
        return;
    }
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

int rnk(int ql,int qr,int &i,int l,int r){
    if(!i) return 0;
    if(ql<=l&&r<=qr) return t[i].v;
    int ans=0;
    if(ql<=mid) ans+=rnk(ql,qr,ls,l,mid);
    if(qr>mid) ans+=rnk(ql,qr,rs,mid+1,r);
    return ans;
}

int kth(int k,int &i,int l,int r){
    if(l==r) return l;
    if(t[ls].v>=k) return kth(k,ls,l,mid);
    else return kth(k-t[ls].v,rs,mid+1,r);
}

int n;

signed main(){
    cin>>n;
    while(n--){
        int op,x;
        cin>>op>>x;
        if(op==1) update(x+MOV,1,root,1,MOV<<1);
        if(op==2) update(x+MOV,-1,root,1,MOV<<1);
        if(op==3) cout<<(rnk(1,x+MOV-1,root,1,MOV<<1)+1)<<'\n';
        if(op==4) cout<<(kth(x,root,1,MOV<<1)-MOV)<<'\n';
        if(op==5) cout<<(kth(rnk(1,x+MOV-1,root,1,MOV<<1),root,1,MOV<<1)-MOV)<<'\n';
        if(op==6) cout<<(kth(rnk(1,x+MOV,root,1,MOV<<1)+1,root,1,MOV<<1)-MOV)<<'\n';
    }
    return 0;
}

P3834 【模板】可持久化线段树 2

#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 2e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

void update(int p,int v,int &i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

int query(int ql,int qr,int k,int l,int r){
    if(l==r) return l;
    int delta=t[t[qr].l].v-t[t[ql].l].v;
    if(delta>=k) return query(t[ql].l,t[qr].l,k,l,mid);
    else return query(t[ql].r,t[qr].r,k-delta,mid+1,r);
}

int n,m,a[N],b[N];

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=a[i];
    sort(b+1,b+n+1);
    int top=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        int p=root[i-1];
        update(lower_bound(b+1,b+top+1,a[i])-b,1,root[i-1],1,top);
        root[i]=root[i-1],root[i-1]=p;
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<b[query(root[l-1],root[r],k,1,top)]<<'\n';
    }
    return 0;
}

P3567 [POI2014]KUR-Couriers

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 5e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

void update(int p,int v,int &i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

int query(int ql,int qr,int v,int l,int r){
    if(l==r) return l;
    int lsiz=t[t[qr].l].v-t[t[ql].l].v,rsiz=t[t[qr].r].v-t[t[ql].r].v;
    if((lsiz<<1)>v) return query(t[ql].l,t[qr].l,v,l,mid);
    if((rsiz<<1)>v) return query(t[ql].r,t[qr].r,v,mid+1,r);
    return 0;
}

int n,m,a[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int p=root[i-1];
        update(a[i],1,root[i-1],1,n);
        root[i]=root[i-1],root[i-1]=p;
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<query(root[l-1],root[r],r-l+1,1,n)<<'\n';
    }
    return 0;
}

P1972 [SDOI2009] HH的项链

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e6+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

int update(int p,int v,int i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return i;
    if(p<=mid) ls=update(p,v,ls,l,mid);
    else rs=update(p,v,rs,mid+1,r);
    return i;
}

int query(int ql,int qr,int vl,int vr,int l,int r){
    if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
    int res=0;
    if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
    if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
    return res;
}

int n,m,a[N],last[N],top[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        last[i]=top[a[i]];
        top[a[i]]=i;
    }
    for(int i=1;i<=n;i++) root[i]=update(last[i],1,root[i-1],0,n);
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<(r-l+1-query(l,r,root[l-1],root[r],0,n))<<'\n';
    }
    return 0;
}

P4587 [FJOI2016]神秘数

#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 2e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

int update(int p,int v,int i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return i;
    if(p<=mid) ls=update(p,v,ls,l,mid);
    else rs=update(p,v,rs,mid+1,r);
    return i;
}

int query(int ql,int qr,int vl,int vr,int l,int r){
    if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
    int res=0;
    if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
    if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
    return res;
}

int n,m,a[N];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) root[i]=update(a[i],a[i],root[i-1],1,1e9);
    cin>>m;
    while(m--){
        int ans=1,l,r;
        cin>>l>>r;
        while(1){
            int res=query(1,ans,root[l-1],root[r],1,1e9);
            if(res>=ans) ans=res+1;
            else break;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

P3293 [SCOI2016]美味

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 2e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

int update(int p,int v,int i,int l,int r){
    t[++tot]=t[i];i=tot;
    t[i].v+=v;
    if(l==r) return i;
    if(p<=mid) ls=update(p,v,ls,l,mid);
    else rs=update(p,v,rs,mid+1,r);
    return i;
}

int query(int ql,int qr,int vl,int vr,int l,int r){
    if(qr<l||ql>r) return 0;
    if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
    int res=0;
    if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
    if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
    return res;
}

int n,m,a[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int N = *max_element(a+1,a+n+1);
    for(int i=1;i<=n;i++) root[i]=update(a[i],1,root[i-1],0,N);
    while(m--){
        int b,x,l,r,ans=0;
        cin>>b>>x>>l>>r;
        for(int i=20;~i;i--){
            if(b&(1<<i)){
                if(!query(ans-x,ans-x+((1<<i)-1),root[l-1],root[r],0,N)) ans+=(1<<i);
            }
            else{
                if(query(ans-x+(1<<i),ans-x+((1<<(i+1))-1),root[l-1],root[r],0,N)) ans+=(1<<i);
            }
        }
        cout<<(ans^b)<<'\n';
    }
    return 0;
}

P2617 Dynamic Rankings

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e6+5;
int n,m;
int a[N];

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

void update(int p,int v,int &i,int l,int r){
    if(!i) i=(++tot);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

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

void update(int p,int v){
    for(int i=p;i<=n;i+=lowbit(i)) update(a[p],-1,root[i],0,1e9);
    a[p]=v;
    for(int i=p;i<=n;i+=lowbit(i)) update(a[p],1,root[i],0,1e9);
}

int lr[N],rr[N],tl,tr;

inline void split(int l,int r){
    l--,tl=0,tr=0;
    for(int i=l;i;i-=lowbit(i)) lr[++tl]=root[i];
    for(int i=r;i;i-=lowbit(i)) rr[++tr]=root[i];
}

int kth(int k,int l,int r){
    if(l==r) return l;
    int siz=0;
    for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
    for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
    if(k<=siz){
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
        return kth(k,l,mid);
    }
    else{
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
        return kth(k-siz,mid+1,r);
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int j=1;j<=n;j++){
        cin>>a[j];
        for(int i=j;i<=n;i+=lowbit(i)) update(a[j],1,root[i],0,1e9);
    }
    while(m--){
        char op;int x,y,z;
        cin>>op>>x>>y;
        if(op=='Q'){
            cin>>z;
            split(x,y);cout<<kth(z,0,1e9)<<'\n';
        }
        else update(x,y);
    }
    return 0;
}

P3380 【模板】二逼平衡树（树套树）

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e5+5, INF = 2147483647;
int n,m;
int a[N],b[N],btot;

struct node{
    int v,l,r;
} t[N<<10];
int tot,root[N];

void update(int p,int v,int &i,int l,int r){
    if(!i) i=(++tot);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

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

void update(int p,int v,bool clear=true){
    if(clear){for(int i=p;i<=n;i+=lowbit(i)) update(a[p],-1,root[i],1,btot);}
    a[p]=v;
    for(int i=p;i<=n;i+=lowbit(i)) update(a[p],1,root[i],1,btot);
}

int lr[N],rr[N],tl,tr;

inline void split(int l,int r){
    l--,tl=0,tr=0;
    for(int i=l;i;i-=lowbit(i)) lr[++tl]=root[i];
    for(int i=r;i;i-=lowbit(i)) rr[++tr]=root[i];
}

int kth(int k,int l=1,int r=btot){
    if(l==r) return l;
    int siz=0;
    for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
    for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
    if(k<=siz){
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
        return kth(k,l,mid);
    }
    else{
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
        return kth(k-siz,mid+1,r);
    }
}

int rnk(int v,int l=1,int r=btot){
    if(l==r) return 1;
    if(v<=mid){
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
        return rnk(v,l,mid);
    }
    else{
        int siz=0;
        for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
        for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
        return siz+rnk(v,mid+1,r);
    }
}

struct Query{
    int op,x,y,z;
} qs[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int j=1;j<=n;j++){
        cin>>a[j];
        b[++btot]=a[j];
    }
    for(int j=1;j<=m;j++){
        cin>>qs[j].op>>qs[j].x>>qs[j].y;
        if(qs[j].op!=3){
            cin>>qs[j].z;
            if(qs[j].op!=2) b[++btot]=qs[j].z;
        }
        else b[++btot]=qs[j].y;
    }
    sort(b+1,b+btot+1);
    btot=unique(b+1,b+btot+1)-b-1;
    for(int i=1;i<=n;i++){
        int v=lower_bound(b+1,b+btot+1,a[i])-b;
        update(i,v,false);
    }
    for(int i=1;i<=m;i++){
        int op=qs[i].op,x=qs[i].x,y=qs[i].y,z=qs[i].z;
        if(op!=2&&op!=3) z=lower_bound(b+1,b+btot+1,z)-b;
        if(op==3) y=lower_bound(b+1,b+btot+1,y)-b;
        if(op==1){
            split(x,y);cout<<rnk(z)<<'\n';
        }
        if(op==2){
            split(x,y);cout<<b[kth(z)]<<'\n';
        }
        if(op==3) update(x,y);
        if(op==4){
            split(x,y);
            int pre=rnk(z);
            if(pre==1) cout<<(-INF)<<'\n';
            else{
                split(x,y);cout<<b[kth(pre-1)]<<'\n';
            }
        }
        if(op==5){
            split(x,y);
            int pre=rnk(z+1);
            split(x,y);
            int nxt=kth(pre);
            if(nxt!=z&&pre<=(y-x+1)) cout<<b[nxt]<<'\n';
            else cout<<INF<<'\n';
        }
    }
    return 0;
}

标签：return,int,线段,mid,cin,详解,ls,权值,define
From： https://www.cnblogs.com/zheyuanxie/p/wsgt-codes.html

相关文章

  • 权值线段树详解
    前言首先明确，权值线段树是线段树的一个子集。它的思想与线段树一模一样，只是实现的功能更加神奇。前置知识：线段树树状数组本文将介绍权值线段树、可持久化权值线段树......
  • Java并发——ThreadLocal详解
    引言ThreadLocal的官方API解释为：“该类提供了线程局部(thread-local)变量。这些变量不同于它们的普通对应物，因为访问某个变量（通过其get或set方法）的每个线程都有自己......
  • mysql 数据导入导出命令详解
    一、导入导出场景及简单用法都是基于文本文件导入：mysqlimport-usystem-p-S/usr/local/mysql/data/mysql.socktest--fields-terminated-by=','/usr/local/mysql/tt3......
  • 【YBT2023寒假Day3 C】樱桃莓莓（凸包）（线段树）
    樱桃莓莓题目链接：YBT2023寒假Day3C题目大意给你一棵有根数，点有a,b两种权值。然后一个点的分数是它以及它所有祖先的a权值和的绝对值乘上b权值和的绝对值。然后......
  • Airtest步骤详解
    录制脚本touch：点击事件，在设备窗中选中对应图标，或者填入点击的坐标swipe：滑动事件，选中图标滑动或填入滑动前后的坐标位置sleep：等待事件，填入等待时间（单位是秒）......
  • private,protected,public,partial详解
    https://blog.csdn.net/weixin_34242509/article/details/93440590private，只有类内可直接访问，protected，类内和子类可直接访问，public，谁都能直接访问。继承类型意思是说把父......
  • 算法：线段树&&Luogu p3372题解
    前言不愧是线段树，竟然卡我这么久，还是那句话：十年OI一场空，不开longlong见祖宗#1什么是线段树？线段树长什么样？通俗一点，线段树就是线段，树。实际上，线段树是一棵完全......
  • 18.3 SQL Server事务与锁详解之（事务篇）
    SQLServer事务与锁详解之（上篇）-事务目录SQLServer事务与锁详解之（上篇）-事务简介事务的基本知识事务ACID特性事务分类事务并发数据访问事务并发带来的一致性问题丢失更新......
  • tcp/ip详解之04 以太网和802.3封装
    1.以太网和802.3封装在TCP/IP世界中，以太网IP数据报的封装是在RFC894[Hornig1984]中定义的，IEEE802网络的IP数据报封装是在RFC1042[PostelandReynolds1988]中定义的。......
  • tcp/ip详解之03 ip首部
    1.ip首部4个字节的32bit值以下面的次序传输：首先是0～7bit，其次8～15bit，然后16～23bit，最后是24~31bit。这种传输次序称作bigendian字节序。由于TCP/IP首部中所有的二进制整......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99