根号数据结构
Argvchs 说我不会根号算法，把之前的博客搬过来，然后再补点东西。
upd：懒得给分块什么的再开博客了，一块扔到这里。
莫队
一种离线算法，可以用 \(O(n\sqrt n)\) 的复杂度处理区间查询问题，当然，也可以带修，下文也会提到。
关于复杂度
莫队优化的关键是排序 + 分块，将每个询问离线下来，按照左端点所在块从小到大排序，假如左端点在同一个块，按照右端点从小到大排序。
处理问题时，我们可以通过移动左右端点来不断更新区间答案，而且排序后前后两个左端点的距离（移动次数）不会超过 \(2\times \sqrt n\) 次，总共 \(n\) 个查询，复杂度相乘也就是 \(O(n\sqrt n)\)。而因为右端点无序，但是固定左端的情况下按升序排列，所以因为左端有 \(O(\sqrt n)\) 块，而右端点一次移动 \(O(n)\) 次，总的也就是 \(O(n \sqrt n)\)。所以，莫队算法的总复杂度就是 \(O(n\sqrt n)\)。
其实，这种排序方式并不是最优解，最优解应该按照曼哈顿距离建最小生成树，但因为本身写这个就是暴力算法，这个也就无所谓了。
一种优化方式，奇偶性排序。在移动莫队指针的过程中，两个询问之间左右移动，可能会出现多余移动的情况，那么我们可以按照奇块正序，偶块反序的方式来排序，可以优化 30% 左右。
P1972 HH的项链
模板，开桶维护区间数个数,虽然加强了数据，卡卡也是能过的。
P1494 小 Z 的袜子
假设有 \(k\) 个相同的数，那么会有 \(\left (_{2}^{k} \right )\) 种选法，总共 \(\sum \left (_{2}^{cnt_x} \right )\) 种，\(cnt_i\) 表示 \(i\) 的数量。区间内随便选一对的方案数是 \(\left (_{2}^{r-l+1} \right )\)，答案就是这俩比一下就完了，之后莫队扩缩区间维护。
P5268 [SNOI2017] 一个简单的询问
记 \(get(l,r,x)\) 表示 \([l,r]\) 区间内 \(x\) 的出现次数，求 \(\sum get(l_1,r_1,i)\times get(l_2,r_2,i)\)。
会发现这个式子很难直接推，考虑做一下差分，\(get(l_1,r_1,x)\) 可以拆成 \(get(1,r_1,x) - get(1,l_1-1,x)\)。
拓展到整个式子(令 \(g(l,x)\) 表示 \(get(1,l,x)\))
做个前缀和，就可以将整个式子当作四个询问，直接莫队统计答案即可。
P4396 [AHOI2013] 作业
这题相对于板子，只是加了个取值在 \([l,r]\) 的限制，对于这个东西，完全可以考虑树状数组，每次莫队扔进树状数组，出来直接前缀和统计答案即可。
复杂度 \(O(n\sqrt n\log n)\)。
带修莫队
在区间问题中，可能会存在修改操作，虽然是离线算法，但莫队也是能做的。
假设普通莫队有 \((i,j)\) 两个维度，表示区间左右端点，那我们可以再加上一维时间维 \((i,j,t)\) 表示区间在第 \(t\) 秒的答案。
P1903 数颜色 / 维护队列
以本题为例，将时间维加入排序，当作排序的第三关键字。莫队操作中，假如当前有一个修改操作，将 \(a\) 位置与 \(b\) 位置交换，将 \(a\) 位置 \(del\)，将 \(b\) 位置 \(add\)。即可，反操作只是将 \(a\)，\(b\) 交换。
树上莫队
现在考虑将莫队放到树上，其实直接按照欧拉序把树扔到一维平面上，欧拉序这东西就是每次深搜走到走回来都记录一下，这东西剖一下就好了，但是 \(lca\) 可能不在一段欧拉序中，所以需要特判，之后做莫队即可。
Count on a tree II
模板题。
P4074 [WC2013] 糖果公园
给定树上 \(n\) 个数，每个数有 \(w_i\) 的权值，区间内第 \(i\) 个数的价值权重是 \(v_i\)，总权值定义为区间内 \(\sum w_i\times v_{cnt_i}\)，每次单点修改或者查询链上价值和。
由于是普通莫队，直接增加/减少上式即可，没什么好强调的，重点的是时间维度的意义，代表的是修改操作的下标，对应修改操作也是原树内固定的，不用再映射，注意欧拉序上的分类讨论，标记数组不要忘记。
回滚莫队
变种莫队，用于处理难以增加/删除的问题，比如区间众数，\(O(1)\) 增加,\(O(n)\) 删除，我们就可以只进行一类操作，通过回滚解决问题，这也将回滚莫队分为只增不删莫队和只删不增莫队，此处先介绍只增不删莫队。
回滚莫队的流程：
-
序列分块，划分出每个询问左右端点的所在块，通过排序使得左端点按所在块排序，右端点根据左端点升序排列。
-
分情况讨论，假如 \(l\) 和 \(r\) 在同一块内，我们可以 \(O(\sqrt n)\) 的处理询问
-
记 \(l\) 和 \(r\) 为莫队操作的区间，假如 \(l\) 和 \(r\) 不在同一块内，\(L\) 和 \(R\) 为左端点所在块的左右端点，\(x\) 和 \(y\) 为询问的左右端点。初始时，令 \(l \gets R+1\)，\(r \gets R\)。
-
介于这种情况下通常认为增加是 \(O(1)\) 的，我们先移动 \(r\) 至 \(y\)，记录下当前答案，然后新建变量，记录 \(l^{'}\) 向左增加的答案，之后统计答案，将 \(l\) 指针删掉来时增加的量，回到 \(R+1\)，实现回滚。
-
当然，这只是一个块内询问的处理方法，假如当前询问与上一次询问不在同一块内，需要重新移动 \(l\)，\(r\) 至 \(R+1\)，\(R\)，或许可以将这种回滚莫队看作对每个块都做一遍莫队。
AT_joisc2014_c 歴史の研究
价值定义为区间内某值出现次数与该值的乘积，每次询问求区间最大价值。
好像比板子还要板，拿这个当板子挺好。
P5906 【模板】回滚莫队&不删除莫队
定义价值为区间内相同值的下标差绝对值，求区间价值最大值。
记区间内每个值出现的最早/最晚出现的位置为 \(min_{a_i}\)，\(max_{a_i}\)，向右增加时，注意需要时刻更改 \(max_i\)，在回滚时，假如当前 \(max_i = i\)，说明已经找到了最靠右的位置，直接清零。
注意莫队的移动顺序和数组清理。
二次离线莫队
大概就是平衡平衡平衡，模板题第一篇题解写的不错。
能够注意到，莫队的指针移动并不依赖于答案，假设移动一次指针带来的贡献计算复杂度为 \(O(k)\)，那么正常莫队的复杂度就是 \(O(nk\sqrt n )\)，如果这个贡献计算的查询可以做到 \(O(k_1)\)，修改可以做到 \(O(k_2)\)，那么二离莫队的复杂度其实是可以做到 \(O(nk_2 + nk_1\sqrt m + n \sqrt m)\)，最后一个是第一遍莫队指针移动的复杂度，前两个则是我们二次离线下来的询问再扫描线带来的复杂度。
这个贡献也需要可差分，不妨设 \(f(x,[l,r])\) 表示 \(x\) 对 \([l,r]\) 区间的贡献，那么以 \(r\) 变为 \(r+k\) 为例，所带来的新贡献就是 \(\sum \limits_{x=r+1}^{r+k} f(x,[l,x-1])\)，我们可以进一步对这个贡献差分，得到 \(\sum \limits_{x=r+1}^{r+k} f(x,[1,x-1]) - f(x,[1,l-1])\)，那么此时，我们就已经将贡献拆成了两个前缀相减，第一个贡献还与 \(l\) 无关，所以我们可以将其预处理，然后离线下来第二个询问，挂到对应端点上跑扫描线就好了。
离线操作时的示例：
l=1,r=0;for(auto &[L,R,ii,id,ans]:Q)
{
if(l>L) A[r].pb({L,l-1,id,1,1});while(l>L) --l,ans-=pre[l];
if(r<R) A[l-1].pb({r+1,R,id,-1,0});while(r<R) ++r,ans+=suf[r];
if(l<L) A[r].pb({l,L-1,id,-1,1});while(l<L) ans+=pre[l],++l;
if(r>R) A[l-1].pb({R+1,r,id,1,0});while(r>R) ans-=suf[r],--r;
}
然后是例题。
P4887 【模板】莫队二次离线（第十四分块(前体)）
给定一个长 \(n\) 的序列，\(m\) 次询问，每次给定 \(l,r\) 表示查询 \(l \le i < j \le j\)，且 \(\text{popcount} (a_i \oplus a_j) = k\) 的数对个数。
\(1 \le n,m \le 10^5,1 \le V < 16384\)。
首先这个问题主观感觉上无法 polylog，于是考虑莫队。
易知 \(a \oplus b = c\)，等价于 \(a \oplus c = b\)，这样，我们只需要开一个桶，对于每一个新加入/删除的数，每次枚举 \(\text{popcount}(a_i \oplus j) = k\) 的 \(j\)，给对应位置加减即可，复杂度 \(O(n \binom{14}{7} \sqrt m)\)，无法通过。
注意到这个问题的插入与查询复杂度及其不平衡，且答案是可差分的，考虑二离莫队。
我们仍然带入 \(f(x,[l,r])\)（推导过程上文已经写了，这里不再赘述），只需要考虑在扫描线时暴力维护区间答案即可，由于每次查询是 \(O(1)\) 的，所以最终复杂度 \(O(n\binom{14}{7} + n \sqrt m)\)，最终扫描线时暴力移动指针是对的，因为它就是莫队指针的移动过程。
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
给定一个长 \(n\) 的序列，\(m\) 次询问，查询区间逆序对数。
\(1 \le n,m \le 10^5,1 \le V \le 10^5\)。
考虑莫队，朴素莫队复杂度是 \(O(n\sqrt n\log n)\)，但是注意到逆序对是可差分的问题，考虑二离莫队。
我们要求尽量快的查询逆序对，于是离散化后值域分块，就能做到 \(O(1)\) 查询，\(O(\sqrt n)\) 修改，可以平衡到总复杂度 \(O(n\sqrt n)\)。
一些细节，注意逆序对是有顺序的，差分时要分开维护。
关于莫队的一些注意问题
奇偶优化回滚莫队是不能用的。
注意莫队移动指针时的顺序：
while(l>q[i].l) add(--l);
while(r<q[i].r) add(++r);
while(l<q[i].l) del(l++);
while(r>q[i].r) del(r--);
第二分块
给定一个序列，完成以下操作：
- 将 \([l,r]\) 内所有 \(>x\) 的数减 \(x\)。
- 查询 \([l,r]\) 内值 \(=x\) 的数的个数。
\(1 \le n \le 10^6,1 \le V \le 10^5\)。
「突刺贯穿第二分块」。
好像模板题只有这个。
考虑到区间值域是单调不降的，我们分块均摊去做这个东西，具体来讲，我们记区间最大值 \(mx\)，对于每一次减法操作：
-
\(mx \le 2x\)，那么我们可以只操作 \([x+1,mx]\) 的值域，然后对每个数开一个并查集维护其跳到谁了，这个操作可以使 \(mx\) 减小 \(mx-x\)。
-
\(mx > 2x\)，那么我们可以操作 \([1,x]\) 的值域，将他们全部 \(+x\)，再打一个整体减法 tag，这个操作可以使得 \(mx\) 减小 \(x\)。
这样均摊下来，每个块的复杂度只有 \(O(V)\)，总的也就是 \(O(V\sqrt n)\)。
然后，我们只需要暴力重构维护散块，整块分类讨论，用并查集维护每个数，就可以解决这个问题。
如果忽略并查集的复杂度，那么总复杂度是 \(O(n\sqrt n)\)，空间复杂度相同，但是本题被卡空间了，逐块处理即可。
浙公网安备 33010602011771号