第一道题 CF1515I Phoenix and Diamonds

题目链接。

题意（5s,1000MB）：
$n$​ 种钻石，一颗第 $i$​ 种钻石重量为 $w_i$​，价值为 $v_i$​，一开始第 $i$​ 中钻石的库存为 $a_i$​。接下来进行 $m$​​ 次操作：

• 1 k d：进货了 $k$ 个种类为 $d$ 的钻石；
• 2 k d：卖出了 $k$ 个种类为 $d$ 的钻石；
• 3 c：如果你有一个大小为 $c$ 的袋子，且按照第一关键字为价值（从大到小），第二关键字为重量（从小到大）的顺序取钻石的话，你最终可以取到钻石的价值为多少（注意操作不会真正执行）。

$1\leq n\leq 2\times 10^5$，$1\leq m\leq 10^5$，$1\leq k,d,a_i\leq 10^5$，$1\leq c\leq 10^{18}$。

由于要放东西，最终复杂度一定与 $c$ 有关，而考虑到 $c$ 非常大，我们可以把物品按照 $[2^{i-1},2^i)$ 进行分块。由于取东西的顺序是确定的，我们可以先排好序，先取的在左，后取的在右。然后我们在查询时先找到 $c$ 的最高位 $w$ ，在线段树查询时，对于当前查询的区间又分为 $4$ 种情况：

1. 该区间只剩下唯一一个物品，尽可能多地塞进去即可。
2. 放得下所有重量不大于 $2^{w-1}$ 的物品，塞进去直接返回即可。
3. 放得下所有重量不大于 $2^{w-2}$ 的物品，但是满足条件的情况下，还想试图放一个 $[2^{w-2},2^{w-1})$ 是做不到的，也可以塞进去直接返回。
4. 否则，递归左右区间（先左后右）。

我们发现，每次塞东西貌似都能够使 $c$ 至少减少一半，因此猜测单次询问的复杂度为 $O(\log n \log c)$。

不会证，但发现这样就过了。感性理解的话，2,3 情况显然满足，猜测第 $4$ 种情况下，我们所能找到的大物品能够使得 $c$ 减半，因此总归能满足。不行就手玩乱搞。

总之，第一种情况，在值域很大且复杂度大概率与值域有关的情况下，可以考虑对于物品的值域进行分块以图在查询时能否使所查询的值域以 $\log$ 的速度减小。

第二道题 P7447 [Ynoi2007] rgxsxrs

题目链接。

题意（6s,64MB）：
给定一个长为 $n$​ 的序列 $a$​，需要实现 $m$​ 次操作：

• 1 l r x：表示将区间 $[l,r]$ 中所有 $>x$ 的元素减去 $x$。
• 2 l r：表示询问区间 $[l,r]$​ 的和，最小值，最大值。

$1\le n,m\leq 5\times 10^5$，$1\leq a_i,x\leq 10^9$。强制在线。

容易想到暴力的线段树做法：

• 区间最大值 $\leq x$，直接退出。
• 区间最小值 $>x$，此时修改并打标记退出。

发现这个做法的问题在于区间会被无限细分，这时可以利用值域分块限制细分的总次数。

我们把值为 $[B^{i-1},B^i)$ 的数放在一个值域块里，对于每个块建立一棵线段树。考虑值域一共被分为 $cnt$ 块，那么由于我们对于一棵线段树进行复杂操作，至少要有 $x \ge B^{i-1}$，否则我们最多是直接在整体域上打一个 tag，也比较省力。因此，我们考虑如果一个数每次减去 $B^{i-1}$，那么其至多减去 $B$ 次就会跌落到下一个值域块，其细分到的最多次数就为 $cnt \times B$。而每次细分到的复杂度为 $\log n$，因此整体复杂度为 $n\log n\times cnt\times B$，又有 $cnt=\log_B 10^9$，因此我们只需要取一个合适的 $B$（例如 $16$），就可以将复杂度控制在一个比较好的范围。

从而得到第二种情况，当操作会被无限细分时，我们可以考虑值域分块来限制操作的范围，从而控制细分的上限。

当然，这么写本题会被卡空间，因此还需要在底层暴力（或者叫底层分块），即：如果当前区间长度小于等于某个设定的阈值 $K$，我们就对这个区间进行暴力下传标记、暴力修改与暴力上传标记。由于线段树底层节点占用空间较大，因此这样的操作可以以大常数为代价换取巨额的空间。

至此，本题就解决了，不过众所周知 Ynoi 卡常非常恶心，所以照这个思路写了之后还要大力卡常才行。