省选之后深刻认识到基础题以及思维题的重要性。
说实话里面的交互构造有些还挺好玩的，怎么感觉像软性颓废。
按主观难度排序。
看四月之前能不能做完 luogu 上有的。
[COTS 2019] 排名 Vezuv
奶龙题，容易用 Trie 表达偏序关系，然后拓扑排序即可。
[COTS 2021] 虫 Kukac
容易想到计算几何的射线法，然后推推细节就做完了。
[COTS 2017] 影响 Utjecaj
删去关键点后，同一连通块内的点等价，变为单点修邻域和，根号分治即可。
[COTS 2023] 下 Niz
考虑扫描线，每次计算 \(r\) 为右端点的贡献。
发现合法的 \(l\) 需要满足 \([l,r]\) 互不相同，最小值为 \(1\)，最大值为 \(r-l+1\)。前两个条件可以双指针找到合法区间。最后一个条件容易用单调栈+线段树维护。
看到题解区有更简单的最值分治做法，我晕。
[COTS 2023] 题 Zadatak
首先可以用异或前的面积与异或后的面积表达出答案，于是只需动态维护面积大小。
假设一个正方形是由原始边长为 \(a_1>a_2>a_3>\cdots>a_k\) 异或得到的，则面积为 \(a_1^2-a_2^2+a_3^2-a_4^2+\cdots\)，这个线段树合并乱搞一下就行了。
[COTS 2018] 直方图 Histogram
求出每个点作为最小值的区间统计贡献。
由于值域太大，枚举矩形的高度没有前途，枚举长度则可以通过笛卡尔树启发式合并将复杂度做到 \(O(n\log n)\)。
[COTS 2023] 传 Mapa
发现最直接的传 \(2N\) 个数有 \(0\) 分的高分，但传 \(N\) 个数就有 \(100\) 分。
考虑多项式插值就刚好 \(N\) 个数，数据范围很小可以暴力，选一个大于 \(10^9\) 的质数在模意义下运算即可。
[COTS 2025] 吸尘 / Usisavač
先假设要回到 \(1\)，则为了清扫每条边至少走 \(2\) 次。
再考虑为了拔插座产生的贡献，如果 \({\rm{len_u}} \leq r\) 显然在遍历 \(u\) 子树时不会产生额外贡献，其中 \(\rm{len_u}\) 是 \(u\) 子树中最远距离。也就是说如果 \({\rm{len_u}} > r\)，\(u\) 到其儿子的边都要再走 \(2\) 次。容易构造出这个下界。
最后考虑不回到 \(1\) 的贡献，即最远的叶子，也即 \(\rm{len_1}\)。
[COTS 2022] 移位 Maliand
由于所有本质不同 \(N\) 种循环移位的 \(f\) 之和为 \(KL\)，所以答案下界为 \(\lceil\frac{KL}{N}\rceil\)。
考虑构造，令 \(S\) 中 \(1\) 连续，则要求 \(T\) 中长度为 \(K\) 的区间内不能有超过 \(\lceil\frac{KL}{N}\rceil\) 个 \(1\)，这是容易构造的。
[COTS 2020] 辣椒 Sadnice
即最小化被砍断的边数，肯定希望 \((N+1)\times (M+1)-1\) 条边均匀分配，下界即为 \(k=\lceil\frac{(N+1)\times (M+1)-1}{N+M}\rceil\)。
调整法构造，在每行放 \(k\) 条竖着的边并尽量错开使得每列比较均匀，比较简单。