数据结构（线段树为主）
题单
首先看题目数据范围，$n \leq 100$ ，这种情况要么说明这道题的时间复杂度是比较高的，要么就和矩阵乘法脱不开关系。
阅读题目之后，我们发现可以应用 Floyd 最短路，也就是矩阵乘法的思想去描述每一轮每一个城市的魔法值。
故这道题应该先用邻接矩阵建图，矩阵快速幂求解。
结果就超时了，考虑通过倍增，二进制分解优化。
预处理时间复杂度 $O(n^3\log n)$ ，单次询问时间复杂度 $O(n^2\log n)$ 。
总结：对于数据范围比较小的图论题要联想到邻接矩阵，对于经常会用到的数据不必重复计算，考虑记录下来优化程序的运行效率。
倍增适合于各种各样的优化，非常实用
快速幂也算是二进制拆分，二进制拆分可以用于快速幂的预处理，还能用于喝果汁那道题
像这种和步数有关的题，应该联想到邻接矩阵，邻接矩阵虽然不常用，但是依然很重要
试着由易到难，一步一步分析。
对于 $k = 1$ 的情况，答案就是两点之间的简单路径，考虑通过树链剖分实现。时间复杂度 $O(n \log n)$
对于 $n \leq 200 $时，可以考虑对于每一个节点，距离不超过 $k$ 的点连无向边，对于每一次询问跑最短路，时间复杂度 $O(q\cdot n^2\log n)$。
这个特殊性质非常的玄学，不知道是给什么算法的，这都不知道，我太菜了。
接着分析 $k = 2$ 的情况，额。
看到题目和数据范围后，不难想到矩阵快速幂求解 $k$ 步内到达某一结点的方案数这一类问题。
但是问题出现了，因为上述做法只能满足 "01矩阵"。
那我们就考虑将这个矩阵转化为 01矩阵不久完事了吗？
考虑给每个节点建立 8 个虚点，我们令 $(i,j)$ 表示距离节点 $i$，$j$ 个距离的点，$(i,0)$ 就代表节点 $i$，我们需要将 $(i, j)$ 和 $(i, j-1 )$ 通过一条有向边连接起来。
若此时有边连向这个节点，且距离为 $d$，那么我们就将它连接到 $(i, d - 1)$ 的节点处就可以了，此时这个邻接矩阵就转化为了 01 矩阵。
时间复杂度：$O((9n)^3 \log T)$
总结：如果一道题目是某类题型的变种，那我们可以将这道题想办法转化为我们熟悉的题型；
简单题。
一眼可以看出这是一个连续段问题，考虑通过线段树解决。
我们需要维护以下信息：
-
perl 左端点开始的连续空房间个数
-
perr 右端点开始的连续空房间个数
-
mx 区间内最长的连续空房间个数
转移和区间最长子序列转移的思想差不多，值得注意的是，题目中要求是最靠左侧的，那么在查询的时候需要有限递归左儿子，接着是左儿子和右儿子，最后才是右儿子。
其余操作和普通线段树无异。
这道题比较重视思维，观察数据范围，很明显是要让我们先预处理，接着以比较小的复杂度进行查询。
考虑如何预处理，通过手推样例可以发现，如果一个二元组是成功的，那么它一定能将上一个成功的二元组弹出，而且一个二元组只可能被一个特定的二元组给弹出。
那么就可以通过栈来维护每一个二元组是由谁将它弹出去的。
时间复杂度：$O(n)$
由于预处理已经花费了 $O(n)$ 的时间，查询操作被压榨成了 $\log$ 级或者是常数级。
由之前的总结可以知道，对于可能会重复用到的数据，我们考虑通过倍增进行优化，这样查询的时间复杂度就变为了 $O(\log n)$ ，可以通过本题。
总结：对于一个数据范围比较大的题，它的最大时间复杂度一般不会超过 $O(n)$，若此时的询问次数也非常多就需要考虑预处理；若一道题目中，大多数情况下，他叫你找的特殊的东西，小于普通的东西，那么这个时候就可以考虑直接从特殊的东西入手（出现次数比较少的入手），弱化在普通的东西上面所花费的时间。
看到这道题，很容易联想到动态规划，考虑定义 $F[i]$ 表示第 $i$ 不跑步得到的最大贡献，很容易得出状态转移方程：
因为造成贡献的是很多个区间，所以考虑在右端点统一进行转移，这样可以做到不重不漏
$$F[i] = \max_{i - k - 1 \le j \le i - 1} F[j] + val(j, i) - (i - j - 1) \times d$$
其中 $val(i, j)$ 表示在区间 $i \sim j$ 连续跑步所产生的贡献。
状态转移方程里面有区间 $\max$ 所以很应该能够联想到使用数据结构优化，但由于 $val(j, i)$ 的存在，我们很难使用数据结构进行转移，注意到对于一个挑战 $(l ,r, w)$ 若我们在完成 $F[r]$ 的计算后，将 $l - 1$ 之前的区间都加上 $w$ ，这样之后从 $F[l - 1]$ 及以前的位置进行转移时，我们能肯定 $l \sim r$ 天之内都跑了步， 从而产生了 $w$ 的贡献。
显然，处理完 $val(j, i)$ 之后，还有 $(i - j - 1) \times d$ 需要处理，我们将其拆开，得到 $i \times d$ 和 $(j - 1) \times d$ 即可，将具有相同变量的放到一起，令 $G[i] = F[i] + i \times d$ ，我们可以得到如下转移方程：
$$F[i] = \max_{i - k - 1 \le j \le i - 1} G[j] - (i - 1) \times d$$
这样就可以使用线段树进行转移了，但是我们还会发现一个问题，数据范围中 $n \le 10^9$ 需要使用离散化，我们把一个挑战 $(l, r, w)$ 转化为 $(l - 1, r + 1, w)$ ，意思是 $l - 1$ 和 $r + 1$ 天不跑，这样就和 $F$ 的含义契合，无需在做处理。
总结：
- 区间问题考虑在右端点统一转移，这样能做到不重不漏。
- 将相同的变量放在一起，使用换元法
思维过程：
- 构思出普通的动态规划
- 联想到使用数据结构进行优化
- 消除 $val(i, j)$ 的影响
- 将离散化和状态联系起来
AC code
括号序列
题单
看到题目，不难想到记忆化搜索。
类比普通的括号序列记忆化搜索，这道题目非常良心，已经帮我们把所有的情况都摆了出来，那么我们就考虑对这些情况进行考虑就足够了。
迅速打完记忆化，发现答案莫名其妙非常大，发现边界条件判断漏，寄了。
总结：若记忆化搜索返回的结果很大，有可能时边界条件没有判断清楚。