总结

太伤心了，晚上的时候忘记白天已经写了一部分总结了，然后用 echo 生成直接覆盖了呜呜呜。

上午

那白天就简要概括一下。上午做了 zgs 说要做的一些题，然后感觉不太熟悉线段树合并。找回了上午的计划。[[树上差分]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

前置模板（Sper OJ）
--------------------------------------------
A1323. 【基础模板】差分 - 二维差分 - 地毯
A1108. 【NOIP模板】树上差分 - 点差分- 松鼠的新家
A1109. 【NOIP模板】树上差分 - 边差分 - 运输计划


【练习赛】
-------------------------------------------------
树上差分：Luogu P3128 [USACO15DEC] Max Flow P
树上前缀和：Luogu P4427 [BJOI2018] 求和


【树上差分-推荐习题】
-----------------------------------------
Luogu P3258 [JLOI2014] 松鼠的新家
Luogu P2680 [NOIP2015 提高组] 运输计划
Luogu P1600 [NOIP2016 提高组] 天天爱跑步
Luogu U143800 暗之连锁
Luogu P4556 [Vani有约会] 雨天的尾巴（前置知识：线段树合并）



【分层图】
----------------
继续上次题目……（似乎还没做）伤心

下午

尝试理解昨日 T4 和其改编来的原题 NOI 2018 情报啥的，失败，不会。但是 pigeon 大佬改出来了，%%%。

晚上

晚上一起打了一场 cf。link 。是 div 1，就很有难度。切了前三道题。讲解一下思路。有一个 A1 和 A2，这里直接讲解 hard version。

Dances (Hard Version)

题目大意。一个长为 n - 1 的 a 数组和长为 n 的 b 数组，枚举一个加入 a 的数从 1 到 m，然后求最大的 k 使得一个 a 的子序列和 b 的子序列一一对应时 a 都小于 b 的 k 的和。（我在说啥？你们还是去看题面吧）。会发现排序后 a 的前几位和 b 的后几位匹配。先二分求出不加入的一个最长的 l，容易发现小于一个数时会是 l + 1，大于后会是 l。那么就将 a 的前 l 位放在 b 的前 l + 1 位开始，一定会有一位开始不满足条件，那么这个地方的 b 值就是临界点。代码：link

Time Travel

虽然写起来不是很难，但是想还是有一点难度的。我最开始想的是分层图，但是会发现同一个时间可能会出现多次，如果暴力 bfs 或 转移会发现如果有一个时间有左右的边而这个时间反复出现就会爆炸。接着我们发现可以在一个地方停留。因此，我们想出了正解。直接把所有边都存在一个点中，我们 dijkstra，到一个点后考虑转移到另一个点。会发现要等到那条边出现的时间的时间才行。因此选择用主席树维护后缀各个时间出现的最早时间。然后就行了。注意细节，最后需要减一，因为到达后不需要再旅行了。时间复杂度差不多两个 log。代码很好写。代码：link