<h2>赛时</h2>

T1 是个带环的博弈，我比较菜不会做 写了无环和有自环的点就跑了。
T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路，拿到了一点点暴力分
T3 一开始不会，发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了，可惜这是在比赛结束前一分钟发现的 [流泪]

最后 T1 不知道为什么爆零了 0+25+50=75，光荣省三。

<h2>题解</h2>

<h3>A. Idioms</h3>

T1 无环的话建反边 dp 是很显然的。设 $f_{i,0/1}$ 是到了第 $i$ 个点，是谁在操作的最优答案。
考虑使用类似于 bfs 最短路的东西来完成这个操作，对于一个状态 $f_{ * ,0}$，我们需要最小值，那么第一个能更新它的肯定是最短的；对于一个状态 $f_{ * ,1}$，我们需要最大值，那么最后一个能更新它的肯定是最大的。我们只需要处理好未更新的状态 就可以去环了。
注意到 $f_{ * ,1}$ 如果没有状态能到（并且不是起点），那么就说明存在一个点未被确定。考虑这些未被确定的状态会构成一个类似于环的东西，说明这些状态形成了稳定态不会受外界干扰。其余同理。
代码

<h3>B. Traffic</h3>

这种题一看就是 $n^2$ 题。。。拆位显然不现实
但是注意到普通的最短路是 $O(n^3)$ 的，无法接受。我们注意到边权都一样（为 $1$），我们自然联想到了 bfs。可是如果不对边进行优化，我们还是要每次遍历 $O(n^2)$ 条边，还是会 T。
我们首先考虑最短路可以长成什么样：一定是从一个点先向右跳非负整数步，再向左跳非负整数步（更加复杂的跳法都可以找到一种简单的不劣的做法）。于是我们考虑先预处理出 $f_{i,j}$ 表示点 $i$ 到点 $j$ 向右走的最短路，然后就只需要考虑向左的边了（便于一个点对其他点的集体更新）。
考虑我们枚举 $j$，那么讨论：

1. $i \geq B_j$，$f_{i,j} = 1$
2. $i &lt; B_j$

这个时候我们需要考虑我们一定是跳到区间 $[B_j,j-1]$ 的某个点上，然后跳回去的。我们可以贪心的去跳到 $B$ 更小的点上（意味着可以用更小的代价跳过去），也就是求 $B_{B_j \cdots j-1}$ 的最小值，从这里转移即可。

然后我们可以考虑最短路：首先我们将有值的点都扔到堆里，然后每次取出最小的点，每次去更新区间。发现一个点只会被更新一次，所以我们用并查集维护哪些点还未被更新，就能保证遍历时间是 $O(n)$ 的了。可是在 $n=6000$ 下 $O(n^2logn)$ 这样要跑 10s...
考虑每次边权递增，并且最短路不超过 $n$，我们将堆换成一个桶，完美的解决了该问题（qwq）
代码

<h2>C. Generator</h2>

可以看成每次插入一个操作，询问这个操作对答案的影响，最后做个前缀和。
考虑 Sub5 的做法：操作在询问之前，维护一个修改操作和询问操作的线段树，插入一个修改操作就在询问线段树上查一下，插入询问类似。
现在考虑顺序不保证了，可以考虑 cdq。
这里的两组限制是 $(插入时间，序列位置)$。
我们可以两边 cdq ，分别考虑插入询问和修改的贡献。我们先考虑第一种：
求询问的贡献，也就是要统计修改的该次询问结果的贡献，满足条件的修改应该

1. 插入时间在它前面
2. 序列位置在它前面

然后直接分治下去就好了，反之亦然。
代码

<h2>总结</h2>

T1 其实没做过怎么消环。。。以后可以考虑一下当 dp 状态建出的转移图边权简单时与 bfs 的关系，并且暴力还打挂了
T2 没有去思考（如果能意识到暴力最短路是错的或许就能去想想 $n^2$ 了），还是自己菜
T3 写的太慢，导致知道正解后没时间写出来
NOIPDay2 如果这么差，再这样下去怕不是省三文化课预定（