数据结构选做
-
\(\texttt{CF319E Ping-Pong}\)
交叉的线段之间的边是双向边，可以用并查集维护。
由于线段长度严格单调递增，只会出现后面的线段包含前面的线段的情况，因此直接用线段树去连边，并查集的正确性可以保证。
对于包含的线段，由于 \(a\in b, b\in c \longrightarrow a\in c\) ，这种单向边最多只走一条，直接最后 \(check\) 一下即可。
时间复杂度 \(\mathrm{O(n \alpha n\log n)}\) 。
\(\texttt{ac记录}\)
-
\(\texttt{CF526F Pudding Monsters}\)
由于每行每列只有一个点，可以将所有的 \((x,y)\) 映射成一个排列 \(p[x]=y\) ，那么一个大小为 \(k\) 的合法子矩阵满足：
\[\max - \min + 1 = k \]考虑计算每个 \(r\) 的贡献，则合法的 \(l\) 满足 \(\max - \min + l = r\)，由于 \([r,r]\) 必然合法，并且 \(\max - \min + l \ge r\)，则有贡献的 \(l\) 满足
\[\max - \min + l = \min\limits_{i=1}^{r}(\max - \min + i) \]用线段树维护区间最小值的个数即可，时间复杂度 \(\mathrm{O(n\log n)}\) 。
\(\texttt{ac记录}\)
-
\(\texttt{CF453E Little Pony and Lord Tirek}\)
将每个位置最近一次被查询的时间记作该位置的颜色，则每次查询最多只会使得序列颜色段数 \(+2\)，并且每查询一段就会使整个序列的颜色段数 \(-1\)，均摊下来查询的颜色段数是 \(O(1)\) 的，可以直接暴力。
考虑一个颜色段怎么做，对于每只??，可以知道她魔力溢出所需的最小时间，开一棵主席树搞搞即可。
时间复杂度 \(\mathrm{O(m\log n)}\)。
\(\texttt{ac记录}\)
-
\(\texttt{[Ynoi2012] NOIP2016 人生巅峰}\)
长度为 \(len\) 的区间的非空子集数为 \(2^{len} - 1\)，观察到 \(v\le 1000\)，那么区间总和至多为 \(1000len\)，根据鸽巢原理，当 \(2^{len}-1\ge 1000len\) 时一定有权值和相同的集合，解得 \(len \ge 14\)，那么只用考虑 \(len \le 13\) 的情况。（权值和相同的集合去掉交集也是相同的，不用再考虑 “\(X,Y\) 没有交集” 这个限制。）
\(len\le 13\) 的情况直接 \(bitset\) 优化背包即可。修改用树状数组记录修改次数，查询倍增即可。
\(\texttt{ac记录}\)