主席树学习笔记

作者:神秘网友 发布时间:2021-01-25 15:37:36

主席树学习笔记

主席树本质上就是在线段树上维护前缀和,一般是建权值线段树来维护区间k大值

先来看模板题:

A. 野生动物园

描述

有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内,这个区域从南到北被划分成N个区域,每个区域 都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai,Ai越小觅食能力越强 。饲养员cmdButtons决定对狮子进行M次投喂,每次投喂都选择一个区间[I,J],从中选取觅食能力值第K强的狮子 进行投喂。值得注意的是,cmdButtons不愿意对某些区域进行过多的投喂,他认为这样有悖公平。因此cmdButtons 的投喂区间是互不包含的。你的任务就是算出每次投喂后,食物被哪头狮子吃掉了。

输入

输入文件第一行有两个数N和M。此后一行有N个数,从南到北描述狮子的觅食能力值。此后M行,每行描述一次投喂 。第t+2的三个数I,J,K表示在第t次投喂中,cmdButtons选择了区间[I,J]内觅食能力值第K强的狮子进行投喂。 1<=N<=100000,1<=M<=50000

输出

有M行,每行一个整数。第i行的整数表示在第i次投喂中吃到食物的狮子的觅食能力值。

样例

输入

复制
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1

输出

复制
3
2

就是求区间k大值,

我们先将每个数的权值离散化,再建n棵权值线段树,

针对l-r里的权值就通过前缀和减一下就好了,

但这样空间复杂度是o(n^2)的,

考虑优化:

每次新建一颗线段树就最多只会出现logn个新节点,于是我们把新的和旧的拼接起来即可

至于寻找k大值,因为前缀和存在单调性,直接用分治的思想来找即可(logn)

总体流程:

1.将所有数离散化

2.建议一棵空的线段树

3.每一次把一个点与线段树连边,多加上logn个点

4.利用分治来找最大值

注意:由于有nolngn个节点,线段树数组必须开nlogn个,一般来说是n<<5

代码:

建树

void build(int l,int r) {
    int p=++cnt;
    int mid=(l+r)/2;
    if(l==r) return;
    build(l,mid);
    build(mid+1,r);
}

加点

int add(int x,int l,int r) {
    int p=++cnt;
    t[p].l=t[x].l,t[p].r=t[x].r,t[p].sum=t[x].sum+1;
    if(l==r) return p;
    int mid=(l+r)/2;
    if(mid>=rk) t[p].l=add(t[p].l,l,mid);
    else t[p].r=add(t[p].r,mid+1,r);
    return p;
}

查询

int ask(int x,int p,int l,int r,int rk) {
    int num=t[t[p].l].sum-t[t[x].l].sum;
    int mid=(l+r)/2;
    if(l==r) return l;
    if(num>=rk) return ask(t[x].l,t[p].l,l,mid,rk);
    else return ask(t[x].r,t[p].r,mid+1,r,rk-num);
}

总代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int rt[N],a[N],b[N],cnt,rk,n,m;
struct data {
    int l,r,sum;
} t[N<<5];
void build(int l,int r) {
    int p=++cnt;
    int mid=(l+r)/2;
    if(l==r) return;
    build(l,mid);
    build(mid+1,r);
}
int add(int x,int l,int r) {
    int p=++cnt;
    t[p].l=t[x].l,t[p].r=t[x].r,t[p].sum=t[x].sum+1;
    if(l==r) return p;
    int mid=(l+r)/2;
    if(mid>=rk) t[p].l=add(t[p].l,l,mid);
    else t[p].r=add(t[p].r,mid+1,r);
    return p;
}
int ask(int x,int p,int l,int r,int rk) {
    int num=t[t[p].l].sum-t[t[x].l].sum;
    int mid=(l+r)/2;
    if(l==r) return l;
    if(num>=rk) return ask(t[x].l,t[p].l,l,mid,rk);
    else return ask(t[x].r,t[p].r,mid+1,r,rk-num);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int q=unique(b+1,b+n+1)-b-1;
    rt[0]=1;
    build(1,q);
    for(int i=1; i<=n; i++) {
        rk=lower_bound(b+1,b+q+1,a[i])-b;
        rt[i]=add(rt[i-1],1,q);
    }
    for(int i=1,l,r,k; i<=m; i++) {
        scanf("%d%d%d",&l,&r,&k);
//    cout<<ask(rt[l-1],rt[r],1,q,k)<<endl;
        printf("%d\n",b[ask(rt[l-1],rt[r],1,q,k)]);
    }
    return 0;
} 

完结撒花

主席树学习笔记 相关文章

  1. ansible系统复习学习笔记-从零到无

    --时间:2021年1月25 --作者:飞翔的小胖猪 前言 该文档仅作为作者复习ansible使用,对格式和流程没有做过多的编排和概述。不喜勿喷。 基础 ansible控制主机是基于python中的Paramiko模板(Paramiko是python对ssh的实现) ,ansible服务端要求系统为linux操

  2. 图机器学习有多大神力一文带你回顾2020展望2021

    新智元报道 编辑:keyu 【新智元导读】 近两年,图机器学习可谓是机器学习研究领域的新星,随着模型的更新和应用的推广,越来越多的人开始把注意力转向了这一方向。过去一年中,图机器学习在哪方面有突破呢,在未来的一年中,哪些分支和方向会成为新的研究趋

  3. IJCAI 2020 已线上开奖!周志华、张成奇还将分别担任2021程序主席和2024大会主席

    新智元报道 来源:IJCAI 编辑:Q、SF 【新智元导读】 2020年IJCAI国际人工智能联合大会于今年1.7-15日在线上召开,组委会在开幕式上公布了IJCAI2020卓越研究奖,Donald E Walker杰出服务奖,AIJ经典论文奖,AIJ突出论文奖,IJCAI-Jair 最佳论文奖,IJCAI杰出

  4. 【笔记】关于多分类问题中的混淆矩阵,精准率

    关于多分类问题中的混淆矩阵,精准率 具体操作 (在notebook中) 使用手写识别数据集,使用全部的样本数据,不做限制,对数据进行分割,使用逻辑回归算法,求解出准确度 import numpy as np import matplotlib.pyplot as plt from sklearn import datasets d

  5. 【算法学习记录-散列】【PAT B1043】输出PATest

    给定一个长度不超过1的、仅由英文字母构成的字符串。请将字符重新调整顺序,按 PATestPATest.... 这样的顺序输出,并忽略其它字符。当然,六种字符的个数不一定是一样多的,若某种字符已经输出完,则余下的字符仍按 PATest 的顺序打印,直到所有字符都被输出

  6. 【笔记】ROC曲线

    ROC曲线 前文讲了PR曲线 这里说ROC曲线,其描述的是TPR和FPR之间的关系 TPR是什么呢,TPR就是召回率 FPR是什么呢,FPR就是和TPR对应的,即真实值为0的一行中的预测为1的部分比例 和精准率和召回率一样,TPR和FPR之间也有着内在的联系,TPR越高,FPR越高,反

  7. Python深度学习笔记09--使用Keras建立循环神经网络

    6.2 理解循环神经网络 6.2.1 Keras中的循环层: 1 from keras.layers import SimpleRNN 2 3 from keras.models import Sequential 4 from keras.layers import Embedding, SimpleRNN 5 6 model = Sequential() 7 model.add(Embedding(10000, 32)) 8 model.ad

  8. 2020ASE-课程总结

    围绕课程理论学习和课程项目实践,总结自己的学习心得体会,整理自己的收获。 在课程之初,正式开始项目之前,写了这门课的第一篇博客——期望与笃信;对自己进行了简单的剖析并提出了自己的目标以及方案计划;总结起来就是,寻求三个方面能力的提升 团队协

  9. 【笔记】F1 score

    F1 score 关于精准率和召回率 精准率和召回率可以很好的评价对于数据极度偏斜的二分类问题的算法,有个问题,毕竟是两个指标,有的时候这两个指标也会产生差异,对于不同的算法,精准率可能高一些,召回率可能低一些,反之一样,真正使用的时候应该根据具体

  10. 【笔记】混淆矩阵,精准率和召回率

    混淆矩阵,精准率和召回率 评论回归算法的好坏点击这里 评价分类算法是不能单单靠一个分类准确度就可以衡量的,单用一个分类准确度是有问题的 比如说,一个癌症预测系统,输入体检信息,就可以判断是否得了癌症,这个系统的预测准确率有99.9%,但是不能说这

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词