倍增值域分块例题

这里引用一下 lxl 学长的 PPT 上的原话，来说明一下倍增值域分块的应用类型：

带时间复杂度的均摊，可以分出两种常见的类型：

每个数被操作一次之后就会减半

每个数被操作一次之后可能减小的很少，操作很多次后减半

对于第一种问题，难点在于如何高效找到每次操作，有哪些数需要被减半

对于第二种问题，常见的解决方法是倍增值域分块

一般问题是的这种形式的问题适合用倍增值域分块解决

这个套路有一定技巧性，得结合具体问题具体分析

CF702F T-Shirts 2800

题目大意

有种 T 恤，每种有价格和品质。

有个人要买 T 恤，第个人有元，每人每次都会买一件能买得起的最大的 T 恤。一个人只能买一种 T 恤一件，所有人之间都是独立的。

问最后每个人买了多少件 T 恤？如果有多个最大的 T 恤，会从价格低的开始买。

解答

这是倍增值域分块的板子题。

首先可以把种 T-shirt 按照优先级排序。然后将个人全部插进一个平衡树里面。每一个节点记录现在的钱数和已经买了的衣服个数。

然后我们每次做修改操作（所有能减少的减少）的时候，就要利用一个 trick：首先把整个平衡树分成 3 块：值域为、、。对于第一块和第三块，我们可以给第三块打一个减少的 lazytag 之后和第一块合并。就算这样第三块的所有数还是大于第一块的所有数。平衡树形态平衡。然后第二块就先暴力修改，然后再暴力插入（注意插入的时候要先分裂，再插入，最后合并！）。

这样的话，因为是值域的被暴力修改，也就是每次暴力修改一个点值域最多减半，也就是每一个节点最多只会修改次。

加上每一次分裂、合并的复杂度为次的。所以最终复杂度就是。

P7447 YNOI rgxsxrs AT Lv.17

题目大意

给定一个长为的序列，需要实现次操作：

1 l r x：表示将区间中所有的元素减去。

2 l r：表示询问区间的和，最小值，最大值。

，。

解答

这里依然使用倍增值域分块的 trick。

首先，我们这里设定使用 2 进制。那么就把整个序列分为。

我们对于每一个区间建一棵下标线段树。每一次的修改操作，我们就要在所有的区间内修改位置。

然后修改了之后我们会发现有一些数它已经不属于原本的区间里了。我们可以暴力倒序遍历所有区间，while 判断是否有数小于，即最小值是否小于。若有，就将其弹出该区间，然后插入区间里面。

查询就遍历区间，累加答案。

因为每一个数最多会被暴力弹出、加入次，每一次修改复杂度。所以最后时间复杂度是双，可以通过此题。

但是！这道题最重要的一点就是它卡空间，空间 64MB，就相当于是必须线性！

于是我们就可以利用一个新的 trick：底层分块。也就是，对于每一个线段树叶子节点，它的父亲对于的范围必须大于一个给定块长。修改如果递归到叶子节点，就在这个长度上暴力修改。

块长为，那么线段树节点就只有个。再设棵线段树，就只有个节点了。

不过这样会被卡时。只需要把设定从 2 进制改成 32 进制就可以了。

P9069 YNOI TEST_98 AT Lv.16

题目大意

给定一个长为的序列，有两种操作，共次：

给定，对于所有满足且，。
给定，求对于所有满足且，的和。

。

解答

成功拿下全机房首杀！

只不过调了一个晚上 + 一个上午o(TヘTo)

和前面那道题思路类似，依然是倍增值域分块（或加上底层分块，这道题不卡空间，所以写不写均可）。

然后因为，所以对于那些已经变成负数的数，它们只需要用一个线段树维护即可。

但是，这道题要注意的是，我那个调了一天的点，就是 change 操作的时候要剪枝！

void change(int x, int l, int r, int ql, int qr, ll val){

    if(tr[x].len == 0) return ;
+   if(tr[x].maxi == tr[x].mini && tr[x].mini == val) return ; // 这一行一定要加上，否则就会像我一样一直被卡在 75pts 动不了！
    if(ql<=l&&r<=qr&&(tr[x].maxi<val||tr[x].mini>val)) return modify(x, val), void();
    if(r-l+1<=S){
        rebuild(x, l, r, ql, qr, val, 0);
        return ;
    }
    pushdown(x);
    int mid = l+r>>1;
    if(ql<=mid) change(x<<1, l, mid, ql, qr, val);
    if(qr>mid) change(x<<1|1, mid+1, r, ql, qr, val);
    pushup(x);
}

P8522 IOI2021 Dungeons AT Lv.16

题目大意

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

Robert 正在设计一款新的电脑游戏。游戏中有一位英雄、个敌人和个地牢。敌人从到编号，地牢从到编号。敌人（）处在地牢，其能力值为。地牢里没有敌人。

英雄一开始进入地牢，初始能力值为。每次英雄进入地牢（）时，都需要面对敌人，且会发生以下情况中的一种：

如果英雄的能力值大于等于敌人的能力值，那么英雄会胜出。这使得英雄的能力值增加（）。这种情况下，下一步英雄将会进入地牢（）。

否则英雄会战败，这使得英雄的能力值增加（）。在这种情况下，下一步英雄将会进入地牢。

注意可能会小于、等于、大于，可能会小于、等于、大于。无论对战结果如何，敌人始终处在地牢，且能力值为。

当英雄进入地牢的时候，游戏结束。可以看出无论英雄的起始地牢和初始能力值如何，游戏一定会在有限次对战之后结束。

Robert 希望你通过次模拟来对游戏进行测试。对于每次模拟，Robert 输入英雄的起始地牢和初始能力值。你需要做的是对于每次模拟给出游戏结束时英雄的能力值。

你要实现以下函数：

1	void init(int n, int[] s, int[] p, int[] w, int[] l)

：敌人的数量。
、、、：长度为的序列。对于每一个（）：
- 是敌人的能力值，也是击败敌人后英雄增加的能力值。
- 是英雄被敌人击败后增加的能力值。
- 是英雄击败敌人后进入的下一个地牢的编号。
- 是英雄被敌人击败后进入的下一个地牢的编号。
恰好调用此函数一次，且发生在任何对如下的 simulate 函数的调用之前。
1
int64 simulate(int x, int z)
：英雄的起始地牢编号。
：英雄的初始能力值。
假设英雄的起始地牢编号为，初始能力值为，函数的返回值是相应情况下游戏结束时英雄的能力值。
恰好调用此函数次。

对于所有数据：

（对于所有的）
（对于所有的）
（对于所有的）

解答

我们可以给值域分块。先以为 base。然后预处理块。

我们处理当现在的能力值的时候。因为跳有限次是可以跳到终点的。所以我们可以倍增跳。

我们预处理为当现在在位置时，能力值在范围内，跳条边会跳哪里去。容易发现，当时，那么这次就一定可以战胜，然后跳至。当时，那么这次就一定不能战胜，跳至。否则，是两种可能都存在。而在这个位置获胜了之后，就可以跳至值域为的块内。

这时为了确定它到底是跳还是，我们设一极值为当现在在位置时，能力值在之内，跳条边，并且可以全部按照设定路线跳所需的最大能力值。这里的设定路线指的是，当时，跳，否则跳。

然后为了更新能力值，我们设，为当现在在位置 ……按照上述路线跳条边所可以获得的能力值。

这三个数组都可以在 init 操作时预处理。

然后就是 simulation 函数。这里就枚举，当现在的还没有跳到时，从大到小枚举现在的，也就是跳条边的。若在的范围内，能跳则跳。枚举完之后，就再按照规则再跳一格，若获胜，就相当于是从这个块内跳出去了，进入下一个块。这种跳块的次数就最多就次，那么复杂度双。