LXL 根号数据结构

区间逆序对

常用的做法是莫队 + 树状数组，还有二离莫队，还有分块。

其实我们可以用扫描线的角度考虑，我们对每个点维护右下角被点亮的点数，查询一条线右边的点权和，右端点右移时矩形加。

KDT 即可单根号。

莫队

莫队可以解决两个自由度，相比扫描线解决一个自由度来说更好用。

顺便，dsuontree 实质上是子树不删除莫队，扫描线实质上是前缀莫队。

P7882 [Ynoi2006] rsrams

$q$ 次询问区间子区间绝对众数的和，没有则 $0$ ，绝对众数是次数 $>n/2$ 的数。

$n,q\le 10^6,8\text{ seconds}$ 。

首先众数杀手一下，相等是 $1$ 不等是 $-1$ 求前缀和后逆序对，每个数掏出 $3cnt$ 个可能合法的位置，这个比较好的写法有：

从左往右扫，每个数找到左边第一个非该颜色位置，再从右往左扫，每个数找到右边第一个非该颜色位置。
从左往右扫，不断向右找到第一个和变为负的位置，再找到本程的最后一个 $1$ ，不断向左，找到第一个和变为负的位置，将本段区间处理。

第二种比较牛，至少不带 $\log$ ，并且常数是理论最优。

经典桥段：莫队一次的复杂度是 $cnt_i\sqrt m$ ，那么直接全用莫队就是 $\sum_{i=1}^ncnt_i\sqrt m=n\sqrt m$ 。

但是莫队复杂度是 $n\sqrt m+m$ ，笑嘻了。

根号分治，出现次数大的用莫队，小的把所有逆序对掏出来跑二维偏序，共 $n\sqrt n$ 个点， $m$ 次查询，扫描线根号平衡一下即可 $n\sqrt n+m\sqrt n$ ，总复杂度 $n\sqrt n+m\sqrt n+n\sqrt m$ 。

P4689 [Ynoi2016] 这是我自己的发明

您正在打 galgame，然后突然家长进来了，于是您假装在写数据结构题：

给一个树， $n$ 个点，有点权，初始根是 1。

$m$ 个操作，种类如下：

1 x 将树根换为 $x$ 。

2 x y 给出两个点 $x,y$ ，从 $x$ 的子树中选每一个点， $y$ 的子树中选每一个点，求点权相等的情况数。

对于 $100\%$ 的数据， $1\le n \le 10^5$ ， $1 \le m \le 5\times 10^5$ , $1 \le a_i \le 10^9,1.5\text { seconds}$ 。

拆成 $\mathcal O(1)$ 段区间对之间的贡献，紧接着拆成前缀之间的贡献。

莫队即可，复杂度是 $n\sqrt m$ ，所以 $m$ 稍大可以接受。

虚树上袜子

对颜色根号分治，对虚树根号分治。

虚树点数 $\ge\sqrt n$ 的可以暴力，现在只需考虑虚树点数 $<\sqrt n$ 的。

小颜色直接拆点对，至多 $n\sqrt n$ 个点对，由于虚树点数 $<\sqrt n$ ，我们把边的贡献拆到根链上，一共 $n\sqrt n$ 次询问，做一个二维数点。

大颜色可以维护 $\le\sqrt n$ 棵树，每棵树都做好树上前缀和，可以直接查询虚树覆盖了多少颜色。

#C. 光符「华光玉」

给定排列 $a_1, \ldots, a_n$ ，共 $m$ 次询问，第 $i$ 次询问给定 $m_i$ 个区间 $[l_j, r_j]$ ， $1 \leq j \leq m_i$ ，满足 $1 \leq l_j \leq r_j \leq n$ ，且 $r_j < l_{j+1}$ 。你需要求出有几个二元组 $(p, q)$ 满足 $p < q$ ， $a_p < a_q$ ，且存在 $1 \leq u < v \leq m_i$ 使得 $l_u \leq p \leq r_u$ ， $l_v \leq q \leq r_v$ 。

$n\le 5\times 10^5,\sum m\le 5\times 10^5,\text{30 seconds}$ ，要求线性空间。

其实是一样的。

对值域分块，对区间个数根号分治。

区间个数 $\ge\sqrt n$ 的可以暴力，现在只需考虑区间个数 $<\sqrt n$ 的。

值域块内贡献只需拆点对，至多 $n\sqrt n$ 个点对，由于区间个数 $<\sqrt n$ ，我们把区间的贡献拆到前缀上，一共 $n\sqrt n$ 次询问，做一个二维数点。

块间贡献可以对每个位置维护一个大小为 $\sqrt n$ 的数组，记录每个块里的点数，然后对序列跑前缀和，对值域跑前缀和，然后每个区间都可以差分出一个 $\sqrt n$ 大小的信息，与前面合并的同时统计块间贡献即可。

空间爆炸了，直接对序列分块，只对整块维护信息，散块暴力枚举出信息然后对值域跑前缀和，就可以合并了。

数点怎么线性空间？每次都是区间枚举，直接询问的时候再枚举就好了。

AT_joisc2016_h 回転寿司

树上每次 k 步不每次带 log

直接搞一个树剖跳，跨链的总共次数是很少的，均摊是对的。