$18Michael$ 搞的题目集锦，刷刷看？
以下均为一句话题解，加 $*$ 表示看了题解的部分。
Round 1
A: Codeforces 1521C
查询 $2\ i\ j\ 1$，分分类就可以在 $\frac{n}{2}$ 次左右找到 $1$。
搞出 $1$ 在哪就可以 $n$ 次做了。
B: Codeforces 1511E
容易发现红蓝可以分开算，并且行与行，列与列间互不影响。
直接预处理一段的贡献，对于每行每列里的每一小段乘上一个系数贡献到答案里即可。
C: Codeforces 1506F
注意到向右向左都是一直走下去的，因此直接斜着分层。
除非两点在同一层，否则一定会走到一个没有消耗的层，那么只有层与层之间的边有贡献。
Round 25
A: Codeforces 1380E
本质上就是：当 $i$ 和 $i+1$ 合并时，答案 $-1$。
考虑将修改离线下来用可持久化并查集维护每个版本，对 $n-1$ 个操作分别二分出生效的时间打个后缀标记即可。
*实际上只需要启发式合并暴力维护即可。
B: Codeforces 1239D
$2-SAT$ 裸题。
*不好好看题没看到两个 $i$ 不能同时选，写了个网络流，实际上用缩点就好了。
C: Codeforces 1334F
原题！！1
D: Codeforces 1208F
*考虑枚举答案，则 $a_i$ 和 $a_j\And a_k$ 是答案的一个子集。
*可以利用高维前缀和，处理出 $S$ 是 $a_i$ 子集的最左位置，以及 $S$ 是 $a_j,a_k$ 子集的最右两个位置。
*从高位往低位贪心，判断一下是否合法即可。
Round 24
A: Codeforces 1042E
排序后暴力 $dp$，把欧几里得距离拆开用前缀和优化即可。
B: Codeforces 1091E
*没看到链接人都傻了。我们有一个 $O(n\log n)$ 的做法，可以判断某个解是否合法。
证明可以对连边有交和包含讨论。
容易注意到，可行的答案是一个区间，并且我们可以利用上面的做法来判断一个不可行的答案是偏大还是偏小。
二分即可。
C: Codeforces 1085F
一个位置将整个序列分成了互不影响的两段。（以下假设这个位置为布）
容易发现，如果一段里有石头或者没有剪刀，那么这一段必定可以。
维护一下两端第一个石头和剪刀，就可以得到合法答案所在的区间。使用线段树来统计区间内的布的个数即可。
D: Codeforces 975E
*重力稳定时，固定的那个点与重心在一条直线上。所以维护重心位置就好了。
*剩下的就只是再维护一下旋转角度。
（计算几何狗都不写）