@994495jj 2017-11-01T13:24:05.000000Z 字数 185 阅读 993

hdu4866（扫描线+可持久化线段树）

201711 （ACM）数据结构---可持久化线段树 （ACM）思想----扫描线

询问强制在线，所以问题在于：对于每个x，如何快速询问？
以高度做权值线段树，x作为时间戳。根据给出的s条线段更新2*s棵线段树。
坑点：查询到叶子节点时，叶子节点存了cnt个，但是我只需要小于cnt个点，这时候直接返回cnt*x[l]即可。

这个讲的清楚一点

- - 201706 2
  - hanabi组队训练2
  - hanabi组队训练1
- - 201707 27
  - cfgym100519H
  - cfgym100519G
  - hdu6041
  - hdu6052
  - HDU6049
  - cfgym100513B证明
  - hdu6035
  - 树链剖分学习
  - cfgym100513C
  - cfgym100729I
  - 数据结构入门讲座
  - cf297C
  - cfgym101252E
  - cfgym101252D
  - ARC 078F
  - 2017杭电ACM集训队单人排位赛 - 6 [Problem 1001]
  - 2017杭电ACM集训队单人排位赛 - 6 [Problem 1009]
  - cfgym101411E
  - 欧拉图入门
  - cf138D
  - Problem 1038 Function Graph（foj内网）（dp+倍增）
  - cf139E
  - Problem 1032 Pixel Picture（foj内网）（dp）
  - 记录（组合数学+dp）
  - 记录（思维题）
  - Problem 1031 TetrisPuzzle（foj内网）
  - 个人训练记录
- - 201708 22
  - hdu6097
  - hdu6158
  - hdu6158
  - cfgym100792E
  - cfgym100792G
  - hdu6155
  - hdu6153
  - cfgym100405J
  - hdu6136
  - hdu6129
  - hdu6138
  - hdu6133
  - cfgym100253E
  - cfgym100253D
  - cfgym100253K
  - cfgym100253C
  - cfgym100443H
  - cfgym100443F
  - cfgym101174A
  - cfgym100002B
  - cfgym100002F
  - hdu6059
- - 201709 3
  - hdu5985（抛硬币求硬币i是幸运的概率）
  - hdu6199 gems gems gems（轮流取石子使差最大/小）
  - cf 840C On the Bench（相邻数乘积不能是平方数）
- - 201710 2
  - UVALive 6302 星际旅行，输出需要买的票
  - 树上添加一条边使得最长路径最短
- - 201711 2
  - Java 20171120
  - hdu4866（扫描线+可持久化线段树）
- - java 1
  - Java 20171120
- - 辅助学习记录 1
  - 个人训练记录
- - （ACM） 1
  - UVALive 6302 星际旅行，输出需要买的票
- - （ACM）BFS 1
  - codeforces 786A Berzerk
- - （ACM）hanabi组队训练 2
  - hanabi组队训练2
  - hanabi组队训练1
- - （ACM）二分 3
  - 树上添加一条边使得最长路径最短
  - codeforces contest 255
  - codeforces 808E Selling Souvenirs
- - （ACM）交互题 1
  - cfgym100253D
- - （ACM）位运算 1
  - ARC 078F
- - （ACM）倍增 1
  - Problem 1038 Function Graph（foj内网）（dp+倍增）
- - （ACM）几何 2
  - cfgym100253C
  - cfgym100002B
- - （ACM）动态规划 7
  - hdu6155
  - cfgym100253K
  - Problem 1038 Function Graph（foj内网）（dp+倍增）
  - Problem 1032 Pixel Picture（foj内网）（dp）
  - hanabi组队训练1
  - codeforces contest 255
  - 华中农业大学第五届程序设计大赛
- - （ACM）动态规划----区间dp 1
  - cfgym100002F
- - （ACM）动态规划----数位dp 2
  - cfgym100443F
  - FZU周练-0530老队员场题解
- - （ACM）动态规划----计数 2
  - cf 840C On the Bench（相邻数乘积不能是平方数）
  - cfgym101411E
- - （ACM）图论----欧拉图 1
  - 欧拉图入门
- - （ACM）字符串----AC自动机 1
  - hdu6138
- - （ACM）字符串----KMP 1
  - hdu6153
- - （ACM）字符串----后缀数组 1
  - hiho 1579（给出sa数组，求符合的字符串个数）
- - （ACM）思想 1
  - hdu6035
- - （ACM）思想----扫描线 1
  - hdu4866（扫描线+可持久化线段树）
- - （ACM）思维 8
  - cfgym100443H
  - cfgym101252D
  - 2017杭电ACM集训队单人排位赛 - 6 [Problem 1001]
  - 2017杭电ACM集训队单人排位赛 - 6 [Problem 1009]
  - 记录（思维题）
  - hanabi组队训练2
  - hanabi组队训练1
  - codeforces contest 257
- - （ACM）思维----构造 1
  - cf297C
- - （ACM）推公式 1
  - codeforces contest 255
- - （ACM）数学 2
  - cfgym100002B
  - cfgym101252E
- - （ACM）数学----fib数列 1
  - 华中农业大学第五届程序设计大赛
- - （ACM）数学----博弈论 6
  - cf138D
  - FZU周练-0529新队员场题解
  - codeforces contest 255
  - codeforces 786A Berzerk
  - 博弈论入门讲座
  - 2017中国大学生程序设计竞赛 - 女生专场
- - （ACM）数学----概率 1
  - hdu5985（抛硬币求硬币i是幸运的概率）
- - （ACM）数学----概率论 2
  - FZU周练-0530老队员场题解
  - FZU周练-0528老队员场题解
- - （ACM）数学----矩阵快速幂 3
  - HDU 5950 Recursive sequence（矩阵快速幂）
  - 2017中国大学生程序设计竞赛 - 女生专场
  - 华中农业大学第五届程序设计大赛
- - （ACM）数学----组合数学 2
  - hiho 1579（给出sa数组，求符合的字符串个数）
  - cfgym100792E
- - （ACM）数据结构 1
  - 数据结构入门讲座
- - （ACM）数据结构----树链剖分 3
  - hdu6133
  - 树链剖分学习
  - cfgym100513C
- - （ACM）数据结构----线段树 5
  - hdu6155
  - hdu6133
  - cfgym100253E
  - FZU周练-0530老队员场题解
  - Pacific Northwest Region Programming Contest Division 1
- - （ACM）数据结构---可持久化线段树 1
  - hdu4866（扫描线+可持久化线段树）
- - （ACM）构造 3
  - hanabi组队训练2
  - hanabi组队训练1
  - FZU周练-0529新队员场题解
- - （ACM）浮点数精度 1
  - cf139E
- - （ACM）计算几何 2
  - cfgym101174A
  - cfgym100729I
- - （ACM）计算几何----圆反演 3
  - hdu6097
  - hdu6158
  - hdu6158
- - （ACM）贪心 2
  - hanabi组队训练2
  - FZU周练-0529新队员场题解
- - 未分类 4
  - 春季讲座安排
  - 不太熟悉的知识点
  - A. Always Online
  - 2017 软工实践团队第一次作业——团队展示
- 以下【标签】将用于标记这篇文稿：
选择主题
- 经典白
- 护眼黄
- 薄荷绿
- 东京夜
- 经典黑

添加新批注

在作者公开此批注前，只有你和作者可见。

私有
公开
删除

回复批注

hdu4866（扫描线+可持久化线段树）

内容目录

选择主题