本次部分选手的成绩存在争议，请自重。我知道共同学习的同学确实会被培养出相似的思维模式，但是这次的提交时间之密集程度我认为超过了“同一种思维模式”可能达到的程度。
T1 狗
考察选手对集合的理解以及基本的聚合分析能力。
其实这道题和讲课的那道题是完全不同的，那道是选两个求交……
算法 1
我会 $\Theta(nq^2)$ 暴力！
预计得分 12 pts.
算法 2
考虑如何快速查询某个元素是否在这个区间里都有。
维护并查集，插入一个元素时如果左右有这一元素，就将其左右合并，维护每个并查集的最左和最右。
时间复杂度 $\Theta(nq + |S|)$ （对于此特殊应用，不带 $\alpha$ 常数）
预计得分 30 pts.
算法 3
考虑在插入单个元素时候对答案的影响，如果把元素插入到 $x$ 处，联系算法 2 我们可以想到，这使得 $l \in [l_{dsu}, x], r \in [x, r_{dsu}]$ 处的答案都 + 1 ，用一颗动态开点的树状数组套线段树即可维护。
当然，这里不能用真正的并查集，因为空间开不下，可以用 $\texttt{set}$ 等维护。
时间复杂度 $\Theta((|S| + q)\log^2 n)$
预计得分 50 pts.
算法 4
基于算法 3 ，对于一段空区间插入元素，可以变通一下，对于所有 $l, r \in [l_x, r_x]$ 的贡献都 +1 。而我们仍然暴力合并，每个原有区间实际上只会被用来合并两次：左一次、右一次。故一次区间修改引发的合并次数是均摊 $\Theta(1)$ 的。
时间复杂度 $\Theta(q\log^2 n)$
空间复杂度 $\Theta(q \log^2 n)$
预计得分 78 pts. ~ 100 pts.
算法 5 (std)
上面这个算法常数略大，而且空间略危险，所以我们考虑先将操作存下来，然后用离线树状数组来实现这个东西，跑得效果简直就像一个 $\log$。
空间复杂度就降到 $\Theta(q\log n)$ 辣！
预计得分 100 pts.
后记：很不幸这道题和前段时间 Codeforces 的一道题中解题思路有所共同，所以做过那道题的人可能想这道题就秒出答案了……然而其实我是先出题后来才打那场比赛的……
为什么会这样呢……明明是我先来的，第一次有了开比赛的打算，又有了好的题目点子，两件快乐事情重合在一起。而这两份快乐，又给我带来更多的快乐。但是，为什么会变成这样呢……我的 OI 怎么就白学了呢……
T2 梨
考察选手对数据结构优化建图的能力。
其实吧，这道题重点只想考察一个优化方法……而且我出完这道题后才发现和 POI 撞了，就当给大家送温暖了……
算法 1
对每个供应商连出 $k_i$ 条边，这些边的费用是 0。对每个原点到供应商的连边，有流的上限 $t_i$ 和费用，而对每天拆点，有下界。跑最小费用可行流
时间复杂度 $\mathrm{MinimumCostFlow}(|V| = \Theta(n + m), |E| = \Theta \left(\sum k_i \right))$
预计得分 45 pts.
算法 2 (std)
考虑优化一些连边。
考虑到供应商仅仅是对一个区间的点连边，我们考虑额外建立一些虚点。
一个方法是造一颗线段树，然后每个供应商只需要连出 $\Theta(\log n)$ 条边啦！
时间复杂度 $\mathrm{MinimumCostFlow}(|V| = \Theta(n + m), |E| = \Theta(n + m\log n))$
当然，你也可以通过 ST 表的形式来维护，那就是 $\mathrm{MinimumCostFlow}(|V| = \Theta(n\log n + m), |E| = \Theta(n\log n + m))$
预计得分 100 pts.
T3 锅
考察选手对傅里叶变换的基本认识，对分治思想的基本理解，对“将执行过程作数据化处理”的推广能力，对分块法的基本掌握。
算法 1
对于每次修改，只考虑本修改对 FFT 后的数组的影响
算法 2
对每次查询，暴力执行过程。
前两种算法并用 $\Theta((q_{\min} + \log n)n)$，预计得分 22 pts.
56 pts. 这个档嘛……就是一个分档，如果暴力写的太强或者正解写的常数太大就是这个分……
算法 3 (因为常数优秀所以成了 std)
考虑对时间进行分块。
设时间块大小 $b$，我们每过 $b$ 次修改就将新的系数数组重新做一遍 FFT ，每次查询对于未纳入 FFT 的修改暴力计算对答案的影响。
发现时间是 $\Theta \left(n\log n \cdot \frac q b + qb\right)$ ，取 $b = \sqrt{n\log n}$ 有复杂度 $\Theta \left(q\sqrt{n \log n} + n\log n\right)$
预计得分 100 pts. ，因为它的常数足够优秀，但是为了追求理性的愉悦，本题原本应该的 std 是接下来这种方法：
算法 4 (废弃的 std)
类比线段树等数据结构，考虑对 FFT 算法的执行流程用数据结构记录下来，
回顾按奇偶性分治，我们可以将二进制数位的逆序建出一颗 01-Trie，但是查值仍然要递归到两个子节点，复杂度似乎没有改善。
考虑我们有上面的两种暴力：
暴力 1 是修改线性，查询立刻的。
暴力 2 是修改立刻，查询线性的。
当子树大小达到了阈值 $2^b$，我们对它使用暴力 1 ，对于不到的时候我们进行分治，此时类似暴力 2 。
这样我们的修改在树上只是走到一个截止的大叶子上然后进行修改，时间 $\Theta\left(2^b\right)$。
我们的查询在树上则要覆盖一些区间，但到叶节点的查询就是立即的，时间 $\Theta \left(2^{k - b}\right)$。
当然，你并不必要真的把这棵树显式地构建出来，另一种理解方法是它在进行一个截半的蝴蝶操作，写起来应该是可以像数列分块一样的。
令 $b = \frac k 2$, $2^b = \sqrt n$ ，时间复杂度 $\Theta(q \sqrt n + n\log n)$ ，预计得分 100 pts.
这个做法可能是我写的常数太大，虽然也能通过，但是跑得反而比按时分块要慢，有哪位哥哥写一个优雅还跑得快的版本呀？
算法 ???
如果你有复杂度优于出题者的算法，欢迎在讨论区发表，出题人十分期望见到 $O(\operatorname{poly} \log n)$ 每次修改的做法。
