rprmq2

本文创建于 2022-03-16 21:37:56，原先内容已基本改动殆尽（有 git 在记录！）。

为什么不先看看 rprmq1 呢？

很神奇啊，一年前有人把这题的一个弱卡常版本搬到了校内赛，然后我被垃圾 OJ 评测机创了很久，一年之后又回来被创了。

感谢 lxl 的 std，以及另外一位 lxl 写的跟 std 一样快的代码。

思路

对时间分块，设块长为 ，然后考虑这个块之前的操作以及这个块内的操作。

对于一整个块的操作，它们将平面分割为了 个操作不同的矩形，而每个矩形内的操作是相同的。所以我们令每个矩形内的最大值表示这个矩形，那么块内变为一个 的子问题。

那么接下来块前的操作即为处理出 的子问题矩形。

块间处理

会 rprmq1 最好，虽然我写这句话的时候还没看过 rprmq1。

按照 轴顺序操作，对于 轴上同一层的矩形，我们按照 轴的顺序遍历里面的操作，然后这一层所有矩形的最大值即为这若干修改操作的历史最大值。

超出这一层之后，我们将历史最值重新设为当前值，并继续下一层的操作，使用线段树维护即可。

如果直接这样做的话，这颗线段树的大小是 的，查询 次 个区间是 的，非常劣。

考虑把线段树做成这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph TD
    1,n -.-> 1,y1-1
    1,n -.-> y1,y2-1
    1,n -.-> y2,y3-1
    1,n -.-> yxn,yxn-1
    subgraph 询问点
        1,y1-1
        y1,y2-1
        y2,y3-1
        yxn,yxn-1
    end
    1,y1-1 -.-> 1,1
    1,y1-1 -.-> y1-1,y1-1
    y1,y2-1 -.-> y1,y1
    y1,y2-1 -.-> y2-1,y2-1
    y2,y3-1 -.-> y2,y2
    y2,y3-1 -.-> y3-1,y3-1
    yxn,yxn-1 -.-> yxn,yxn
    yxn,yxn-1 -.-> n,n

我们把线段树分为两层，上层线段树每个叶子表示一个块，这样这上面的结点数就是 的了，然后每次整体查询的时候只需要遍历即可，复杂度降为 。

修改的时候需要用到下层的线段树（在上层的每个叶子的区间内开正常的线段树），所以是 的。

块内处理

使用 KDT/四分树/离线分治 都可以做到 。

实测分治以外的做法都过不去，分治不会。

过了，但基本没过。

强行分治可以直接对着 KDT 的结构将所有操作一次性下传，但是好像不太好写，主要是还需要按照结构把信息重新上传回来。我看了看 std 好像不是这样的。所以能不能教教分治？

复杂度瞎糊

块间长这样：

块内长这样：

看起来很好，但实际上块内常数老大了跑的非常拉。

然后在 的时候有最优 。

空间复杂度是线性的，故本题空间卡的略紧。

实现

首先你要知道这道题在 Ynoi 里一方面算不太卡常的，一方面算非常卡常的。

主要是如果两部分在大方向上写的跟 std 一样的话应该不太难过，但是如果只是跟 std 时间复杂度一样的话那就非常悲伤，很多细枝末节的实现可以改但是没有哪个比较有效的。

如果您会分治法的话请大胆尝试此题，所以能不能教教分治，否则的话不太建议，当然也能硬卡。

以下都是个人经验，仅供参考。

不过我寻思真的会有人会大力卡这题的常么？

块间

标算的 pushdown 好厉害看不懂。

那肯定要写 zkw 线段树的对吧。

我们注意到我们只关心上层线段树的历史最值，所以下层线段树只需要维护当前的最值和加标记即可，每次对下层操作的时候对上层的对应叶子更新一下历史最值。这个非常重要，写出来一下就少了 运行用时。

清空线段树的时候合理地使用 memset 可以快不少。

虽然看不懂标算的 pushdown，但是我另外有一个神秘的优化，每次下传的时候将当前的历史最大加标记清掉：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Unode{
    ll add,mx,_add,_mx;
    void push(Unode &a,Unode &b){
        if(_add){
            cmax(a._add,a.add+_add);
            cmax(a._mx,a.mx+_add);
            cmax(b._add,b.add+_add);
            cmax(b._mx,b.mx+_add);
            _add=0;
        }
        if(add){
            a.add+=add;a.mx+=add;
            b.add+=add;b.mx+=add;
            add=0;
        }
    }
};

比较搞笑但是确实比较高效。

将历史值重置可以直接暴力扫整个线段树，是 的。

这部分的实现可以很好地锻炼模板泛型的使用，因为空间卡的比较紧，建议写一个简易的 allocator 分配内存，当然要是不想研究高阶语法的话直接写两颗线段树也行。

好像可以 再精细实现一点，对于上层线段树把叶子抠出来，其他的结点不需要记录最值标记。

upd 2023/8/24: 我写出来了，，起飞了！正在考虑连同空间一起优化掉！

块内

分治应当是很快的，但是不会啊！所以能不能教教分治！

考虑这是一个满平面，所以 KDT 和四分树的结构是一样的了，爱写哪个都行，我写的四分树。

然后为了内存连续性，需要写成动态开点的，保证在递归结构上相近的结点在内存上也相近。

对于长宽小于 的矩形转为暴力可以快不少，个人在洛谷上尝试得到了 （不知道为什么洛谷的机子跟我的机子差距巨大）。

不知道为什么我写了一个固定一次 build 然后每次循环清空的跑不过每次都重新递归 build 的。

这部分虽然常数很大，但是没甚么优化空间，不建议在尝试这部分的各种实现上浪费时间。因为空间结构比较神秘，递归改迭代似乎效果不好。

其他

块长我发现 （共 块）比 和 快了 ，不知道是不是因为评测机波动毕竟这题时限挺大的。这个不建议大家参考，要参考就参考调块长时需要精确到个位数。

注意每次对所有询问按照 轴方向排序不要使用 set 这样的 STL 或者暴力 sort（当然有可能手写平衡树会快），不如直接带着编号提前排序好，然后暴力遍历的时候判一下编号对不对。

其他的话，记得写快读快输然后调块长。

如何知道还要卡多少常

建议大家先去 Codeforces 上的弱化版交，如果你的代码在 使用的块长下（洛谷代码不做改动的在 CF 上交）能够跑到 以内再考虑交洛谷。

洛谷没过可以加一个卡时返回当前处理了多少块，注意洛谷对 RE 的返回值是模 的，反正总共也没有 块，如果前面几十块都做不完那还是别搞了。

CODE

好像 lxl 不喜欢题解放代码，所以有需要的话可以找我要。

包括 std 以及另外一位 lxl 写的跟 std 一样快的代码也行。

≡