[bzoj 1503][NOI 2004]郁闷的出纳员（平衡树）

时间：2022-09-05 08:35:39

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1503

分析：

经典的平衡树题，我用Treap做的

下面有几点注意的：

1、可能出现新加入的人的薪水就已经比min低了，这种人不能算入最后的走的人当中，要特判

2、对于整体薪水加加减减不能在每个点上处理，在外面记录一个s表示当前加加减减的总和，那么删除的就是平衡树里面权值小于min-s的所有点了，具体删除的时候就是不断往下面找并删除掉当前根节点和左子树。但注意到后面加入的数是不受前面的加加减减的影响的，所以插入进去是不对的，那么假设读入的是x，那么插入的就是x-s，为什么呢？因为每个点的实际权值是 平衡树的权值+S，所以这样可以保证它的实际权值为x。所以对于查K大的时候，最后的权值也要+S

[bzoj 1503][NOI 2004]郁闷的出纳员（平衡树）的更多相关文章

  1. 洛谷 P1486 BZOJ 1503 NOI 2004 郁闷的出纳员 fhq treap

    思路: 1. 此处的fhq treap的分裂是按照权值分裂然后插入的.将小于k的分为一棵子树,大于等于k的分为另一棵子树. 2. 删除的时候只要将大于等于min的分裂到以root为根的树中,另一部分不 ...

  2. bzoj 1503[NOI 2004] 郁闷的出纳员

    题目大意: 给4种操作 I:添加一个员工工资信息 A:增加所有员工的工资 S:减少所有员工的工资 F:询问工资第k高的员工的工资情况 自己做的第一道splay树的题目,初学找找感觉 #include ...

  3. 数据结构（跳跃表）：NOI 2004 郁闷的出纳员

    郁闷的出纳员 [问题描述] OIER公司是一家大型专业化软件公司,有着数以万计的员工.作为一名出纳员,我的任务之一便是统计每位员工的工资.这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常, ...

  4. NOI 2004 郁闷的出纳员（平衡树）

    题目描述 OIER公司是一家大型专业化软件公司,有着数以万计的员工.作为一名出纳员,我的任务之一便是统计每位员工的工资.这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资 ...

  5. NOI 2004 郁闷的出纳员

    Description OIER公司是一家大型专业化软件公司,有着数以万计的员工.作为一名出纳员,我的任务之一便是统计每位员工的工资.这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常 ...

  6. 【BZOJ 1503】[NOI2004]郁闷的出纳员

    [链接] 我是链接,点我呀:) [题意] 在这里输入题意 [题解] 因为所有人工资同时递减. 所以可以设置一个变化值delta. 然后每个人的初始值为k 则把k-delta加入伸展树中. 会发现del ...

  7. Luogu P1486 [NOI2004]郁闷的出纳员(平衡树)

    P1486 [NOI2004]郁闷的出纳员 题意 题目描述 \(OIER\)公司是一家大型专业化软件公司,有着数以万计的员工.作为一名出纳员,我的任务之一便是统计每位员工的工资.这本来是一份不错的工作 ...

  8. 【NOI】2004 郁闷的出纳员

    [算法]平衡树(treap) [题解] treap知识见数据结构. 解法,具体细节见程序. #include<cstdio> #include<algorithm> #incl ...

  9. BZOJ 1503&colon; &lbrack;NOI2004&rsqb;郁闷的出纳员

    1503: [NOI2004]郁闷的出纳员 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 10526  Solved: 3685[Submit][Stat ...

随机推荐

  1. nginx 日志相关配置总结

    设置位于nginx.conf:         log_format  main  '$server_name $remote_addr - $remote_user [$time_local] &q ...

  2. psql-09表&colon;视图和索引

    视图 由查询语句定义的虚拟表;从视图中看到的数据可能来自数据库中的一张或多张表,也可能来自外部; 使用视图的原因一般有: 使复制的查询易于理解和使用; 安全原因; 表一些函数返回的结果映射成视图; 一 ...

  3. CAN总线通信：实现MIC-3680与F28335 CAN总线通信的设置

    博主原创: 实现MIC-3680与F28335 CAN总线通信的设置(MIC-3680CAN模块滤波使用单滤波模式): CAN2.0A协议: (使用11位标识符) <1>F28335发送, ...

  4. SQL多条件查询

    SELECT a.tel,a.business_code,b.name AS business_name,a.register_time FROM T_RED_USER a LEFT JOIN T_P ...

  5. C Primer Plus之存储类、链接和内存管理

    存储时期即生存周期——变量在内存中保留的时间 变量的作用域和链接一起表明程序的哪些部分可以通过变量名来使用该变量. 注意:生存期和作用域是两个不同的概念. 作用域    作用域描述了程序中可以访问一个 ...

  6. Unity之读取本地图片

    1.下载Opencv for unity. 2.把OpenCVForUnity下的StreamingAssets拖到Assets下. 3.点击Tools->opencv for unity-&g ...

  7. MySQL的create table as 与 like区别&lpar;转&rpar;

    对于mysql的复制相同表结构方法,有create table as 和create table like 两种,区别是什么呢? create table t2 as select * from t1 ...

  8. Ising模型（伊辛模型）

    Ising模型(伊辛模型)是一个最简单且能够提供非常丰富的物理内容的模型.可用于描写叙述非常多物理现象,如:合金中的有序-无序转变.液氦到超流态的转变.液体的冻结与蒸发.玻璃物质的性质.森林火灾.城市 ...

  9. 导航栏转场动画CATransition

    CATransition动画来实现, 下面的代码是跳转到下一个视图: CATransition *animation = [CATransition animation]; [animation se ...

  10. 关于wxpython多线程研究包括&lpar;import Publisher错误研究&rpar;

    作为一个自动化测试人员,开发基本的应用桌面程序是必须的!最近在研究wxpython相关知识,目前看到多线程一块,发现官方文档介绍说:"在线程中不能修改修改窗口属性!",但是实际情况 ...

相关文章