突刺贯穿的第二分块

听说原题现在卡常暴力过不了了？不太清楚 QAQ（记得当时第一次过的就是指令集暴力 QAQ）

嗯那么反正看到 Ynoi 就想到卡常 + 分块，然后听说第二分块是最简单的一个？？（怪诶

好像这个还有一个「瑟尼欧里斯树」的别名？但是怎么想都和树没关系吧（摔

功能

第二分块可以在线解决这样的问题：

对数据的要求是值域不能太大（ $10^5$ 差不多了），毕竟是开在值域上的处理。

下面的话用 $n$ 表示序列长度， $m$ 表示询问个数， $A$ 表示值域大小。

原题题意（CF896E）

给定一个长度为 $n$ 的序列和 $m$ 次上面的操作。数据范围： $n,m,a_i\le 10^5$ ，时限 $3000\texttt{ms}$ ，空间 $500\texttt{MB}$ .

$\quad$ 加强版卡了空间（ $64\texttt{MB}$ ）还扩大了值域（ $5\times 10^5$ ），所以必须离线下来做了~~lxl 属实毒瘤~~。

当然离线下来可以把空间复杂度减到 $O(m+n)$ .

很显然每个区间的最大值是递减的。~~不过好像没什么用~~

先分块，块长度还是传统的 $\sqrt n$ . 然后观察数据范围和操作。应该能想到要在值域上做一些事情。

对于查询而言，我们可以在每个块里都开 $A$ 个结点（相当于值域上的并查集），然后把序列里每个位置存一个指针指向它的值对应的结点。

那么整块的查询就可以直接查 $x$ 对应多个结点有几个指针指过来，散块就暴力找。复杂度 $O(\sqrt n)$ .

然后考虑修改怎么做。对于整块的区间减，可以记录这个块的最大值 $k$ . 一种想法是把 $x+1\sim k$ 的所有值的结点分别和 $1\sim k-x$ 合并：

合并前（假设 $k=8,x=5$ ）：

before merge

合并后：

after merge

但是这样做如果 $x$ 太小或者 $k$ 太大，就会合并出问题：合并到被合并的地方（图中 $k=6,x=2$ ）。

wrong merge

什么时候合并会出错？显然是 $k-x\ge x+1$ .

再次观察修改操作，我们发现将「大于 $x$ 的数全部减 $x$ 」和「将小于等于 $x$ 的数全部加上 $x$ ，然后再区间整体减去 $x$ 」是等价的。因此我们如果对每个块记录一个 tag，区间减时直接修改 tag 就可以了。

因此我们做分类讨论：

$k-x\ge x+1$ 即 $k\ge 2x+1$ 即 $k>2x$ （注意 $k\in\mathbb Z$ ），此时直接合并会出错，需要反方向合并然后打上 tag；
$k-x<x+1$ 即 $k<2x+1$ 即 $k\le 2x$ ，此时直接合并即可。

那么显然这时候的查询就需要考虑一下 tag 了。

那么整块修改的复杂度最坏是 $O(A\times \text{DataStructue})$ 的，其中 $\text{DataStructure}$ 是使用数据结构进行合并的复杂度。同时也很显然可以通过并查集或者链表支持合并操作。如果用并查集，可以证明在这里合并的情况都是 $O(1)$ 的！

至于散块的修改，可以直接暴力把块打散了重构做，复杂度 $O(\sqrt n)$ .

以及并查集不能像平常一样初始化，不然时间会爆…… 然后好像说可以证明直接靠特性初始化为 0 是没有问题的？不会 /kk

细节问题一堆。。。咕了（泪