浅谈一类数据结构问题

pdf以及std：[难题选讲2.zip](http://leanote.com/api/file/getAttach?fileId=5aa7c4fdab644106fa000ec9)
引言：有一类数据结构题型略微奇妙，下面是一个例子。

# CF259 Div1 E. Little Pony and Lord Tirek

**时间限制:3000ms|空间限制:256MB**

半人马提雷克是“我的小马驹：友谊是魔法”第四季最后两集的大反派。在“闪闪王国（上）”中，提雷克从塔他洛斯逃了出来。为了变得更加强大，他还吸取了小马们的魔法。

提雷克的核心技能是法力吸取。这个技能可以吸收一个魔法生物的所有魔力并把它们交给施法者。

现在我们把这个问题简化，假设你有n只小马（编号从1到n）。每只小马有三种属性。

si：时间为0时这只小马拥有的法力值
mi：这只小马可以拥有的最大法力值
ri：这只小马单位时间内回复的法力值

提雷克会给出m条指令，每一条都可以被描述为3个整数：ti，li，ri。表示在时间为ti时，提雷克会从编号为li~ri的小马中吸取魔力（包括li，ri），我们会有序地给出m条指令，请你算出每一条指令之后提雷克可以吸取多少点魔力。

Input
第一行包含一个整数N（1 ≤ N ≤ 1e5）-小马的编号。接下来的n行每行包含三个整数Si， mi， ri（0 ≤ si ≤ mi ≤ 1e5；0 ≤ ri ≤ 1e5），表示 一只小马。

下一行包含一个整数m（1 ≤ M ≤ 1e5）-指令数。接下来的m行包含三个整数Ti， li， ri（0 ≤ ti ≤ 1e9；1 ≤ li ≤ ri ≤ N），表示提雷克的指令。所有的指令在ti递增的顺序下给出。

Output
对于每一个指令，输出一行，包含一个整数：提雷克这一次一共吸收了多少魔力。

Examples
input
5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5
output
25
58
Note：
每只小马从零法力开始。对于第一个指令，每匹小马有5法力值，所以你总共得到25法力值，每一只小马在第一次指令后有0法力值。

对于第二个指令，小马3拥有14法力值，其他小马的法力值等于它们的最大法力值。
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
# 思考时间 |BGM: 
# ♫ Harmony——Aurelleah
# ♫ A Dying World——Marcus Warner
# ♫ To Cloudsdale!——Jyc Row
$\space$
$\space$
$\space$
$\space$
$\space$ 
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$ 
$\space$
$\space$
$\space$
## **当当当当~~~~线段树！**
我们先考虑初始魔法为0的情况，如果直接维护最大法力和单位时间回复速度的话会比较棘手。但是注意到魔法值为0，这样的话我们可以建立线段树，对于每一个区间内的小马按照从0回复满的时间从快到慢排序，这样我们每一次查询时我们在节点上二分找出最后一只回复满的小马，把前面的最大法力值加起来，把后面$\Delta$t时间内回复的法力值加起来就好了。这样我们只需要对每一层的最大法力值做前缀和，对每一层的回复速度做前缀和。但是注意到如果这样做的话，该区间内所有小马最后一次被吸取的时间必须相同（如果最后一次吸收的时间不同的话没有办法通过从0回复满的时间求出答案）。那么对于整块的区间我们可以统计，那万一不整块呢？

当然递归向下统计啊！复杂度？注意到你统计完当前区间当前所有的小马最后一次被吸收的时间都会变成当前时间。感性理解一下，还是$O(n log^2 n)$的！这样我们记录一个节点区间最近被修改的时间，如果有小马最近被修改的时间不一样，当前区间记为-1 。遇到-1往下递归，回来时更新最近被修改的时间就行了。

那么如果有了初始值呢？暴力呗~

注意到如果一些小马被榨干魔法，相当于回到了全部为0的状 态，我们这时候就把有初值的区间标记为-2，对于标有-2的区间暴力找完之后更新最近被修改的时间就好了。
时间复杂度：构建$O(n log^2 n)$，查询$O(n log^2 n)$。

于是CF一道E题就做完啦？
于是CF一道E题就做完了。
是不是感觉做了假的E题？

赶快去A一个把。

Rockdu's Blog

导航

最近发表

大佬们的友链