题解：P7711 [Ynoi2077] 3dmq

yinianxingkong · 2024-04-25 21:05:38 · 题解

[Ynoi2077] 3dmq

前言

本篇题解重构过一遍，这一次同时囊括 O(n\sqrt n) 空间和 O(n) 空间做法，您可以通过博客检索快速跳到对应难点。

前排提醒：O(n) 被卡常了，正在申诉，如果想过请写 O(n\sqrt n) 做法。

看笔者这么辛苦给给赞吧 QWQ。

注意，根据惯例，本题解不给代码。有需求私信。

实际上是还没卡过常。

前置知识

操作分块。

了解原理即可，通过对操作分块使本来只能静态重构的数据结构可以支持“动态操作”。

典型例题：P6578 [Ynoi2019] 魔法少女网站。

二维分块

这个比较重要，在这题里面占很大部分。

主要作用是平衡复杂度。

典题是 P7448 [Ynoi2007] rdiq 和 P8530 [Ynoi2003] 博丽灵梦。

三维数点

三维问题肯定是扫描线加带修二维数点，而这里的二维数据结构实验二维分块。

本题会实现 4 种二维分块，接下来会一一讲解。

就是博丽灵梦。

就是 rdiq。

这个时候每个散块期望只会获得 O(1) 个点，直接暴力即可。

参照前面整块做法，直接分 O(\sqrt n)-O(\sqrt n) 的块即可。

O(n\sqrt n) 空间

操作分块，分为三个部分。

注意每个部分都只能 O(n) 时间。

前缀查询

假设维护好了 b 权，对 O(\sqrt n) 个询问贡献 O(n) 个点，点坐标分别为排列，显然采用第一种二维分块。

前缀重构

将块内修改贡献到点上，可以转换成对 O(n) 个点统计多少修改有贡献。点坐标分别为排列且修改 O(\sqrt n) 个，显然采用第二种二维分块。

块内贡献

一个修改操作 (x_1,y_1,z_1,w) 对查询操作 (x_2,y_2,z_2) 贡献：

三维偏序。但容易发现很鬼畜，不能满足一般的性质，只能借助数据随机。

先借助第三种二维分块处理整块和小散块的贡献，难点就在横竖散块。把询问挂上去对每个块扫描线，以竖散块为例，横坐标因为在同一块里范围 O(\sqrt n)，纵坐标因为一定会改整个块是 O(\sqrt n)。每个竖块期望获得 O(\sqrt n) 个点与 O(n) 个询问，所以期望 O(n)，使用第四种二维分块。

O(n) 空间

难点在优化掉挂询问到块上这一步。思路很简单，就是强行定序消除重复项，然后查询时暴力遍历一遍。这里我定的序是时间序较小的询问贡献时间序较大的询问，并且竖散块所属块编号较大。

实现

可以用正常的操作分块实现，但这题为了实现方便，我们对 z 权排序询问，暴力找时间维度，相当于自动做了扫描线。

代码

可以找我要，两种都有。

后记

做这道题不如玩原神。

你怎么知道我边熬夜边写这题边玩原神然后歪迪卢克了？