数据结构

【模板】可持久化平衡树

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):
  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)
  3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)
  6. 求x的后继(后继定义为大于x,且最小的数,如不存在输出2147483647)
和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化) 每个版本的编号即为操作的序号(版本0即为初始状态,空树) (更多…)

DefFrancis
数据结构

二逼平衡树(树套树)

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 查询k在区间内的排名 查询区间内排名为k的值 修改某一位值上的数值 查询k在区间内的前驱(前驱定义为严格小于x,且最大的数,若不存在输出-2147483647) 查询k在区间内的后继(后继定义为严格大于x,且最小的数,若不存在输出2147483647) 注意上面两条要求和tyvj或者bzoj不一样,请注意 (更多…)

DefFrancis
数据结构

[USACO07DEC]美食的食草动物Gourmet Grazers

题目描述

约翰的奶牛对食物越来越挑剔了。现在,商店有M 份牧草可供出售,奶 牛食量很大,每份牧草仅能供一头奶牛食用。第i 份牧草的价格为Pi,口感为 Qi。约翰一共有N 头奶牛,他要为每头奶牛订购一份牧草,第i 头奶牛要求 它的牧草价格不低于Ai,口感不低于Bi。请问,约翰应该如何为每头奶牛选 择牧草,才能让他花的钱最少? (更多…)

DefFrancis