标签 - 平衡树

? 解题记录 ? ? 洛谷 ? ? 平衡树 ? ? 凸包 ?    2018-04-27 21:51:34    450    0    0
题目描述近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务: 给出你所有的A国城市坐标 A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了 A国上层询问对于剩下要保护的城市,修建防线的总经费最少是多少 你需要对每次询问作出回答。注意单位1长度的防线花费为1。 A国的地形是这样的,形如下图,x轴是一条河流,相当于一条天然防线,不需要你再修建 A国总是有两个城市在河边,一个
? 解题记录 ? ? 洛谷 ? ? Splay ? ? 平衡树 ?    2018-01-16 08:01:32    373    0    0
题目描述请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏 中的下划线‘ _ ’表示实际输入文件中的空格) 输入输出格式输入格式:   输入文件的第 1 行包含两个数 N 和 M,N 表示初始时数列中数的个数,M 表示要进行的操作数目。 第 2 行包含 N 个数字,描述初始时的数列。 以下 M 行,每行一条命令,格式参见问题描述中的表格   输出格式:   对于输入数据中的 GET-SUM 和 MAX-SUM 操作,向输出文件依次打印结 果,每个答案(数字)占一行。   输入输出样例输入样例#1: 复制9 8&nb
? 解题记录 ? ? 洛谷 ? ? Splay ? ? 平衡树 ?    2017-12-28 12:11:53    545    0    0
题目描述OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。 工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样
? 解题记录 ? ? 洛谷 ? ? Splay ? ? Treap ? ? 模板 ? ? 平衡树 ?    2017-11-22 23:30:14    484    0    0
题目背景这是一道经典的Splay模板题——文艺平衡树。 题目描述您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1 输入输出格式输入格式:  第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2,⋯n−1,n) m表示翻转操作次数 接下来m行每行两个数 [l,r] 数据保证 1≤l≤r≤n   输出格式:  输出一行n个数字,表示原始序列经过m次变换后的结果   输入输出样例
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 分块 ? ? Splay ? ? 模板 ? ? 平衡树 ?    2017-10-24 19:21:49    745    0    0
题目描述如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式输入格式:   第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。 接下来M行每行包含3或4个整数,表示一个操作,具体如下: 操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k 操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和   输出格式:   输出包含若干行整数,即为所有操作2的结果。   输入输出样例输入样例
? 解题记录 ? ? BZOJ ? ? Splay ? ? 树套树 ? ? 平衡树 ?    2017-09-21 21:18:12    349    0    0
  对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。 Input 输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。   Output   输出包含m行,依次为删除每个元素之前,逆序对的个数。 Sample Input 5 4 1 5 3 4 2 5 1 4 2Sample Output 5 2 2
? 解题记录 ? ? BZOJ ? ? Splay ? ? 线段树 ? ? 树套树 ? ? 平衡树 ?    2017-09-17 11:47:24    394    1    0
Description您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:1.查询k在区间内的排名2.查询区间内排名为k的值3.修改某一位值上的数值4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)5.查询k在区间内的后继(后继定义为大于x,且最小的数) Input第一行两个数 n,m 表示长度为n的有序序列和m个操作第二行有n个数,表示有序序列下面有m行,opt表示操作标号若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数若opt=3 则
? 解题记录 ? ? 洛谷 ? ? Splay ? ? 替罪羊树 ? ? Treap ? ? 模板 ? ? 平衡树 ?    2017-07-21 10:06:08    428    0    0
题目描述您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询x数的排名(若有多个相同的数,因输出最小的排名) 查询排名为x的数 求x的前驱(前驱定义为小于x,且最大的数) 求x的后继(后继定义为大于x,且最小的数)输入输出格式输入格式: 第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6) 输出格式: 对于操作3,4,5,6每行输出一个数,表示对应答案 输入输出样例输入样例#1:10 1 106465 4 1 1 317