Regions

根据地区内的人数大于根号和小于根号分治即可。

[IOI2009] Salesman

线段树维护即可。

[CQOI2018] 异或序列

莫队即可。

Drazil and His Happy Friends

首先，对于 $\bmod \gcd(n,m)$ 不同的男女生互不相关，所以可以先规约为 $n,m$ 互质的情况。

这个问题可以泛化为多源最短路问题，而多源最短路可以视作多个单源最短路取 $\min$，所以去考虑一开始只有一个男生 $x$ 是快乐的情况。

不难发现，$(x+m)\bmod n$ 男生在第 $m$ 秒变为快乐，$(x+2m)\bmod n$ 在第 $2m$ 秒变为快乐……这和女生已经无关了！所以应该去把男女生分开考虑然后取 $\min$（一个初始快乐的女生对男生的影响，可以把她转化为她对面的男生是初始快乐的，这同时也带来了上述结论的正确性）。

现在单独去考虑男生的 $\max$。而男生唯一有用的信息其实 $x'=(x\cdot m^{-1}\bmod n)$，把所有男生按照 $x'$ 排序，那么可能作为最值的只有每个关键男生的前面一个男生，断环成链做一下就好了。

[THUPC 2023 初赛] 种苹果

用一个 LCT 维护，每个结点上维护 splay 子树内对应点的权值排序后的结果。若子树大小小于根号，则直接存下；否则不存，在询问的时候再递归下去。这个做法的可拓展性极强，可惜过于麻烦，在序列上劣于分块，在树上却很优秀。

还有一种办法是用 Linshey 分块，再加上根号重构。感觉码量很大。

[IOI2009] Hiring

先不考虑总钱数最小的限制，因为第二个限制很弱，只要二分一下就能去掉。

对于每个选中的工人，他提供的限制是：$W\cdot \frac{Q_k}{\sum Q}\ge S_k$，也就是 $\sum Q\le X\cdot\frac {Q_k}{S_k}$，按照 $\frac{Q_k}{S_k}$ 排序，从大到小枚举其比值最小的一个，剩下的一定是贪心选 $Q$ 最小的，直到不能选了为止。用堆维护即可。

怎么把二分的 $\log$ 去掉？比值和比值排序的结果是固定的，直接枚举比值最小的工人，对应贪心选出尽可能多的工人，再算出这些工人对应的最小总工资即可。

【清华集训2015】V

吉老师线段树板子题。

事实上，$a_i=\min(B,a_i+A)$ 类型的标记是符合结合律的，可以直接用懒标记来维护。

【清华集训2015】Flea

一个想法是，求出 $f(1),f(m)$，并求出这两条抛物线的交点 $(x,y)$，再求出 $f(x)$，若 $f(x)=y$ 的话，直接返回 $y$；否则，向 $[1,x],[x,m]$ 两边递归下去，这样需要 $2n-1$ 次。

事实上，我们只需要每次取出最高的一个交点向下递归，如果不能向下递归就输出答案，这样就只需要 $n+1$ 次了；最后一次是细节讨论可以优化掉的。

【JOISC2020】扫除

考虑由修改操作构成的序列，一次查询，相当于询问一个点，经过了操作 $[l,r]$ 后，会在哪一个点。

对修改序列分块，散块容易处理，整块的话，平面会被分成 $O(n^{0.5}\times n^{0.5})$ 份，需要对每一份分别预处理出它会移动到哪里。

预处理：考虑分治下去，$T(m)=2T(\frac {m}2)+m^2\rightarrow O(T(m))=O(m^2)$，所以递归下去加上双指针的复杂度是正确的。

询问时：离线，并预处理一个长度为 $O(n)$ 的数组记下双指针的结果，就可以去掉 $\log$，总复杂度 $O(m^{1.5})$。

事实上，这个做法没有完全利用上题目性质，一个性质是：

对于所有操作过至少一次的点，都满足 $x_i<x_j \Leftrightarrow y_i>y_j$。

所以，对于每个还没有操作过的点单独维护，剩下的点就是一个单调栈的形状，随便维护。