DQS DQS

2017年10月

[BZOJ1045] [HAOI2008] 糖果传递 中位数

in 算法,其他 read (75)
Description 有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 第一行一个正整数nn<=1'000'000,表示小朋友的个数. 接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数. O...

线段树合并学习笔记

in 算法,线段树&&树状数组,数据结构 read (134)
被Splay的启发式合并的坑爹常数坑了无数次之后决定学习一下新姿势… 一些证明 正确性前提:对于同样值域的权值线段树,它们的结构是相同的。 所以可以同时递归处理,合并两子树可以直接把两子树根节点信息合并。 复杂度证明:两个线段树合并时,如果一个为空则返回另一个。否则递归合并...
雷姆
拉姆