P3569 KAR
如何判断某个卡牌顺序能否通过反转形成一个单调不降的序列？
使用贪心。我们将第一张卡牌翻到更小的一面。对于后面的卡牌，若小的一面大于等于前一张卡的当前面值，则翻到小的一面。
否则若大的一面大于等于前一张卡的当前面值，则翻到大的一面。仍不满足则无解。
为了对付单点修改操作，我们对序列建一棵线段树。
线段树上每个结点维护两个值，分别表示这个区间的第一张卡牌翻到小的面和大的面时，通过如上贪心过程得到的最后一张卡牌的面值。若无解，则记为-1。
合并时，同以上贪心决策即可。最终，根据根节点的两个值是否都为-1，判断是否有解。
复杂度 \(O((n+m)logn)\)。
P3579 PAN
\([a,b]\) 内存在 \(k\) 的倍数，等价于 \(k \lfloor \frac{b}{k} \rfloor>=a\)。这是因为 \(k \lfloor \frac{b}{k} \rfloor\) 是不超过 \(b\) 的最大的 \(k\) 的倍数。
考虑枚举最大公因数 \(g\)。由上 \(g\) 合法等价于 \(g \lfloor \frac{b}{g} \rfloor>=a\) 且 \(g \lfloor \frac{d}{g} \rfloor>=c\)。
则对于所有 \(\lfloor \frac{b}{g} \rfloor\) 和 \(\lfloor \frac{d}{g} \rfloor\) 都相等的 \(g\)，我们只需要其中最大的一个。我们可以用略作改变的整除分块做到这一点。
复杂度 \(O(\sqrt{b}+\sqrt{d})\)。