Chtholly

题意 维护一个序列 \(s\)，有以下操作。 区间加。 区间覆盖。 求 \(l\) 到 \(r\) 的第 \(k\) 小元素。 求 \(l\) 到 \(r\) 的每个元素的 \(x\) 次方之和膜 \(y\)。 输入由给定种子 随机 生成。 Sol 珂朵莉树。 本质上就是拿 \(set\) 乱搞。 ......

原题 是一个完全不困难的题，但里面一个性质没有想到QwQ 性质：最大值一定在两个部分之一(显然) 于是我们二分答案后，\(O(n^2)\)的找到从左下角开始包含最大值且极差\(\leq x\)的所能覆盖的最大区域，然后判断另一个区域极差是否\(\leq x\)即可 不一定从左下角开始？旋转\(4\) ......

原题 翻译 Chtholly可爱捏 我们先考虑如果\(n \cdot c \leq m\)我们要怎么做，我们可以发现里面一定存在一个数出现了\(\geq \lceil \frac{m}{c} \rceil\)，不妨设这个数为\(x\)，因此我们只需要把所有数都改成\(x\)就可以了 等等好像不对，我 ......

分块。我们先来考虑修改对整块的影响。记值域为 $V=10^5$。 考虑对每一块维护 $V$ 个集合 $S_1,S_2,\cdots,S_V$，第 $i$ 个集合 $S_i$ 维护了区间中所有 $=i$ 的元素的一些信息，并维护区间的最大值 $m$，对于一次操作 $x$： - 若 $m\le 2x$， ......