闲话
比赛地点：广州市第六中学。鹭江-B 口 右手边。
Day1 坐反地铁一站，并走错到东门，喜提晚到 10min。
Day2 去上个厕所，喜提比赛开始后 1min 进入考场。
Day1 看一圈题后发现 124 都是比较好做的，2h 写完后把 T3 写了一下，怎么写这么臭。
Day2 看一圈好难啊，先把 T3T4 过了，然后想了一下 T2，后面突然会 T1 了。
最后 D2T1 没检查正确性挂了，喜提 400+315 rk4。
接下来是题面与题解。
Day1
D1T1
- 题意：
给你一个序列，每次询问翻转一个区间，问序列的价值。询问互相独立，即询问结束后序列会归位。
序列价值定义为 \(\sum_{i=2}^n \max(0,a_{i-1}-a_i)\)。
维护前缀和，\(O(n+q)\)。
D1T2
- 题意：
给定一个边带权的树，给定了 \(a_{(u,v)},b_{(u,v)}\)，你需要求出：
- 其中 \(F(S)\) 是边集 \(S\) 的最大匹配，要求没有匹配边相邻。
维护 \(\sum F\times val,\sum val\)，贪心匹配即可。\(O(n)\)。
D1T3
- 题意：
给定一个 \(n\times m\) 的表格，\(a_{i,j}\) 表示第 \(i\) 个人在第 \(j\) 道题的得分，每道题的满分都是 \(K\)，每道题的得分都是 \([0,K]\) 的整数。
有一个奶龙初始不知道所有的分数，你可以选择告诉这个奶龙若干个 \(a_{i,j}\)。这样被告知的位置是确定的，而其他位置奶龙可以随意决定。要求，奶龙只会报告恰好 \(R\) 个潜在冠军，你需要最小化告知分数位置个数。
\(nm\le 3\times 10^5,R\le n\)。
显然一个人是潜在冠军的条件是，对于他的所有未公开分数，全部填成 \(K\)，而其他剩下的人全部填成 \(0\)。
令 \(S_i\) 表示第 \(i\) 个人的已公开分数，\(C_i\) 表示第 \(i\) 个人未公开的题目数量。
那么考虑 \(S_i+C_iK\ge \max S_j\)，其中 \(j=i\) 也没有关系。
潜在冠军一定从大到小公开分数，而其他人从小往大公开分数。
所以可以枚举 \(\max S_j\)，每个人如果公开 \(j\) 道题，会对于一段区间内的 \(\max S_j\) 进行贡献，贡献形式是这个人是不是潜在冠军，以及对应的最少公开题目数量。这个可以对于 \(O(m)\) 个区间处理出来。
这样我们对 \(\max S_i\) 扫描线，维护对应的对顶堆，就能知道每个 \(\max S_i\) 的答案。
整个题复杂度 \(O(nm\log nm)\)。
其实一个潜在冠军，如果不是 \(\max S_i\)，那么不公开就好了。应该可以少写很多东西。
D1T4
- 题意：
定义 \(f(b_{1 \sim m})=\begin{cases} 0 & m=1\\ f(b_{1\sim x})+1 & m>1 \end{cases}\)
其中 \(x=\max \{ i。
给定一个序列 \(a_{1\sim n}\)。每次给定一个区间 \([l,r]\)，问 \(f(a_{l\sim r})\)。
显然每次一定跳到区间最大值或者区间最小值，那么可以无脑写一个分治做法，\(O(n\log^2 n)\)。
能不能更厉害一些？考虑跳两步以后一定跳到区间最大值或者最小值。
假如跳到了最小值，那么下一步一定去最大值，以此类推，类似一个折线状物。
那么按照 \(l\) 扫描线，维护单调栈即可。 \(O(n\log n)\)。
Day2
D2T1
- 题意：
有一个网格图 \(n\times n\)，每个 \(a_{i,j}\) 在 \([0,P)\) 内随机生成，其中 \(P\) 是 \(\le 10^7\) 的素数。
你需要从 \((s_x,s_y,s)\) 走到 \((t_x,t_y,t)\)，若最短路超过 \(16\) 报告无解。
每步的走法是： \((\pm 1,\pm 1,(val+a_{x,y})^2 \bmod P)\)。
考虑正着跑和反着跑，反着期望是 4 个出边所以复杂度 \(O(4^8)\)。
D2T2
- 题意：
将给定的 \(a\) 划分为若干等差子序列，每个子序列长度至少为 2，最小化公差最大值。\(n\le 3500\)
显然子序列长度不会超过 3，并且 2,3 的子序列分别不交，所以可以直接 dp，需要考虑一些 2,3 的段相交的情况。 复杂度 \(O(n^2\log n)\)，用 vector+二分会快很多。
D2T3
-
题意： 有一个游戏，两个人 A 和 B 玩。初始有一个序列 \(b\)，两人轮流选择恰好一个操作，不能操作者输：
- 操作 1：删除一个数，序列长度减少 1。
- 操作 2：将序列重排为一个以前没有出现过的排列。
现在给定序列 \(a_{1\sim n}\)，每次给定 \([l,r]\)，问 \(a_{l\sim r}\) 是谁赢。
考虑第一步 A 怎么决策，如果排列数是偶数，那么初始用了一个，还剩下奇数个。
如果当前排列是必胜的，我们直接操作就好了。否则，我们重拍序列，如果 B 重排我们继续重排。这样我们把必败态转给对手。
具体而言：\(\binom{n}{o_1,o_2,o_3,\cdots}\bmod 2=1\Rightarrow \bigcup o_i=n\)。
所以如果 \(\bigcup o_i\ne n\)，那么就是必胜的。
如果排列数是奇数，我们不希望转换到偶数的情况，否则 B 就赢了。 那么当前满足 \(\bigcup o_i=n\)，令 \(o_i\) 减 1，仍然满足 \(\bigcup o'_i=n-1\)，那么这要求 \(n\bmod 2=1\)，并且操作的 \(o_i\bmod 2=1\)。
所以，当且仅当 \(\bigcup o_i=n \land n\bmod 2=0\) 时，B 获胜。
接下来是如何求这个东西，显然颜色数超过 \(\log n\) 没有意义。
然后可以猫树，维护 \(\log n\) 个颜色的出现次数，复杂度 \(O((n+q)\log n)\)。