分治与分块
重制版笔记，很多地方还留了坑。。
其中穿插了重量平衡树
分治
CDQ 分治
本质上是考虑左边对右边的影响，问题变成了先加入再查询的问题
离线算法
处理 D 维数点时间是$O(nlog^{D-1}n)$
D 维数点用KDTree：$O(n^{\frac{D-1}{D}})$
D 维数点用Bitset：$O(\frac{Dn^2}w)$*
加点，给定$a , b$查询最大的$ax+by$
本质上是维护动态凸壳 *
直接set维护
记录全局变量，做插入的时候按照 x 比较，做询问按照斜率比较
因为set里面x递增，斜率也递增
CDQ 分治
solve( l , r ) ，先 solve( l , m ) solve( m + 1 , r )
然后就变成了静态问题，左边点加进去，右边的询问。
静态凸壳！
右边斜率排序，然后类似归排扫一遍就好了。
CF 848C
维护每个数字的位置和上一次出现的位置，价值是 i - pre i
一段区间的价值就是$\displaystyle\sum_{l\leq i \leq r , pre[i] \geq l} i - pre[i]$
本质上类似差分
修改本质上只会修改 pre 指向这个点的，这个点，还有它的prev，只会改变三个值。
带修改的二维数点本质上是三维数点，时间是一维。$O(nlog^2n)$
可以写一下
分治FFT
前段时间学过吧
uoj 50
求解微分方程$f’(x) = f^2(x) p(x) + 1$
算出来的式子是$\displaystyle \frac{1}{n} \sum_{0\leq i+j\leq n-1} f_if_jp_{n-1-i-j}$
分治吧，貌似就是分治fft套路
先solve( l , m )
然后考虑新求出的左边的值对右边的贡献
然后就要用$f_{l…mid} f_{0…r-l} p_{0…r-1}$卷起来
然后就把$m+1…r$更新进$f_{m+1…r}$
式子可能有点小锅（比如+1-1啥的），需要再推一下。。
线段树分治（暑假讲的叫时间分治）
离线动态图连通性
把每条边的存活时间放到序列上，然后就可以在线段树上dfs，撤销并查集解决问题
这里要按大小合并，才可以让撤销的量很少
可以LCT维护删除时间的最大生成树，也是离线
对每个物品，求不包含它的背包 方案数
线段树分治
solve( l , r , f ) f 表示 把$l , r$外面的物品加入的数组
$f_1$表示$f$中加入 mid + 1 … r 的物品
$f_2$表示$f$中加入 l … mid
然后递归下去$O(nwlogn)$一个物品会被加入$logn$次
城市建设
修改边权，求MST和
还是可以对时间建立线段树，求出每个边存活时间
LCT 一个 log，线段树分治一个 log，很慢，不需要动脑子
修改一条边边权实际上只会影响MST一条边
随着修改MST变化是很少的
$solve(l,r)$表示$l , r$的修改
整个MST只会改$O(r-l)$边，其他大多数边是不变的
能不能把会变的边拿出来跑MST？
假设边集（l…r修改的边）是$S$，先把其中边设置为 +inf
把这些边和剩余的边跑MST，然后现在不在MST中的边就可以删除了。
因为这些边只会变小，只会把MST的边给拖出来
现在边数边成了$O(n + |S|)$
然后再设置成 -inf，再跑一次MST，现在在MST中的边一定最后也在MST中
点数变成了$O(|S|)$，因为这些边已经可以用并查集并起来了。
而$n$其实是上一层的点数，也就是$O(2(r-l))$
所以这一层的复杂度也是$O(r-l)$的
$T(n) = 2T(\frac{n}{2}) + O(nlogn)$
$O(nlog^2n)$这里的 log 是排序
有点难写吧（可以写一下
核心思想：修改影响的边数量很少
二进制分组
二项堆
一种可并堆，和二进制分组的思想类似。
$T_k$表示的堆是$T_{k-1}$再挂了个$T_{k-1}$，然后节点数量就是$2^{k-1}$
11个数字的二项堆就是一个点数为 8+2+1的森林
合并两个二项堆就是类似二进制+法。
合并是$log$的
删除元素，其实也是合并，比如从16的堆删除就是 1,2,4,8, 的堆和剩下的堆合并。
维护向量序列，支持末尾加入元素，末尾删除元素，求$l,r$和$(x,y)$的最大点积
二进制分组解决的问题往往是，重构很简单，插入删除很麻烦的东西。比如凸壳这种东西，重构直接做，但是插入删除很难。
如果只有增加的话，加入当前有21个元素，我们记做三组 16 + 4 + 1
每组都建一个数据结构，支持区间查询，并且重构很快（线性就很优秀），插入删除很慢。
你往后面加入一个元素，就和前面一步一步合并（重构）过去，比如刚刚那个21的例子，加入一个元素就是 16 + 4 + 2
这样的结构数量必然是$log$，如果在某个结构查询复杂度是$Q(n)$那么查询复杂度就是$Q(n)logn$
重构的复杂度假如是$n$那么每一个元素最多会被重构$logn$次，所以，总复杂度是$nlogn$
重构是均摊$logn$的
既然支持区间操作，可以对每个区间建个线段树，暴力build线段树也是$nlogn$
复杂度是$nlog^2n$的
其实也可以看作建了一棵大的，点数是2的次幂的线段树，当一个点下面的所有叶子都被填了值才把它建出来。本质上是一样的。
二进制分组怎么删除呢？其实整个序列如果画成一棵树的样子（大概就是版本树之类的？）删除就是往父亲跳，加入就是新加儿子。所以问题本质上就是给你棵树，求某个点到根上的一段的点积的最大值。
树剖是$O(nlog^3n)$对询问排序可以去一个log，反正好像不优秀
题解做法好像是点分
直接线段树强行搞是不行的，你删除一个插入一个….在一个块的左右反复横跳就挂了
其实可以搞成随机的，每个点随机一个权值如果比上一个小就合并。
对于一个块被建出来，如果这个块有东西被删除了，就记个标记表示这个块是坏的。
查询如果查到一个坏的块（节点）就到左右递归继续查。
我们希望保证每层只有一个坏的块
如果结尾一直在最后那个坏块动来动去没啥问题
但是如果你的结尾移到了前一个块，那么意味着最后面那块被删光了，那么还是只有一个坏块
但是如果结尾移到了后一个位置，下一个块被建了，那么我们可以直接重构前一个块。
还不是很明白，想清楚了再继续写吧。。
整体二分
子矩阵查询 kth n 500 q 50000
直接二分的话，需要查询子矩阵比某个数大的个数
整体二分，就是拿所有询问一起二分
我们需要看哪些询问权值是大于$\frac{w}{2}$的，哪些是小于等于$\frac{w}{2}$的
这个比较简单的方法是把小于等于$mid$的标1，然后前缀和
然后我们就把询问分成了$0…\frac w 2$,$\frac w 2 + 1$
就这样分治下去
但是每一次分治$n^2$肯定是不行的，必须做到每层$n^2$
每次分治其实我们只需要把$l…mid$加进去然后做查询
对于每个询问就是二维数点的问题。
其实貌似顺次递归来做，就直接是对的了吧。。
所以对于分治到$l,r$复杂度就是$O(|A|+|Q|logn)$$A$为这里的点集
复杂度是$(n^2+Q) log^2(n^2)$
单点修改区间 kth
二分到$l,r$把一个数字从$a$到$b$就是$x$这个位置 少$a$多$b$
可以看自己以前的代码吧$nlog^2n$的
ZOJ2112 这题由于空间限制只能整体二分
给$l , r$的vector 放进去个 k 求 l , r kth
整体二分就变成区间+了 貌似就是那个 任务查询系统 以前挂了好久的题
CF 102354 B
给定 a , b 两个1…n 排列，求$c[k] = MAX_{(i,j)=k}|a_i-b_j|$
$c[k] = MAX_{(i.j)=1}|a_{ik}-b_{jk}|$
其实我们只要求了$c[1]$问题就解决了
因为$c[k]$本质 就是$a_k,a_{2k},…,a_{\lfloor\frac n k \rfloor}$和$b_k,b_{2k},…,b_{\lfloor\frac n k \rfloor}$来跑$c[1]$
枚举$i$就要求最大的$b_j , (i,j) = 1$，因为最大最小是对称的我们求最大的就好了。
整体二分，分治到$(l,r)$，就是知道$a_i$的最大的值在 l,r 间。
我们按照 值在$mid + 1…r$的下标是否存在与当前$a$互质的把$a$分成两份分别跑二分下去。
然后问题就是，统计值在$mid + 1 … r $的下表$j_t$是否存在与某个下标互质。
对于$a_i$下标$i$，需要统计
莫反一下
然后我们可以枚举$d$，给每个$d$统计一下在$A$里面的倍数个数，并且把$\mu(d) \times cnt$放到作为它倍数的$i$里面。这题可以写一下QWQ
决策单调性
由于没怎么写过决策单调性，可能有很多问题QAQ
就是存在最优的方案决策单调。一般都是打表找的规律。
首先，四边形不等式$w(a,d) + w(b,c) \geq w(a,b) + w(c,d)$
假设有$i , k , l , j$， 如果决策不单调意味着$i$转移到了$j$而$k$转移到了$l$
如果满足了上面那个式子，相交的两条边优于了包含的边，所以就满足了决策单调性。这大概就是实质了吧？
四边形不等式是 $O(n^2)$的而不是$O(nk)$准确的说是$O(n(n+k))$
同时，四边形不等式可以优化二维dp的转移，
满足四边形不等式后，假设$dp[l][r]$决策点是$p[l][r]$，那么
其实本质就是交错的路径优秀于包含的路径
但是还要注意，虽然四边形不等式可以推出决策单调，但是决策单调不能推出四边形不等式。
CF 321 E & 诗人小G （其实没怎么听到题的做法，听了决策单调性优化dp的实现方法）
下面是几种搞决策单调性的方法
这里可能还需要再听一下
$solve( l , r , p , q )$表示 i 再$l , r$最优决策是$p , q$之间
我们可以先算$mid$位置的决策点 op 然后，就可以
$solve(l,mid,p,op) , solve(mid+1,r,op,q)$
这样复杂度是$O(knlog_2n)$这样不容易挂。
其实也可以二分单调栈。考虑我们如果求出了$dp[1]$那么后面最优都是从 1 转移过来
现在求出了 2 ， 从 2 转移最优的构成了一个后缀。于是我们可以用单调栈维护每个点可以决定的区间。先从后往前找看能不能整个替代，到达具体区间后再二分。复杂度也是一个$log$但但是不如前一个好写。
其实是可以$O(nk)$的，然而我看不懂 SMAWK
CF 868 F
暴力分治，$solve( l , r , p , q )$
分治下去的时候端点的移动总量是$O(r-l+q-p)$级别的。
把指针从$p$移动到$mid$并且不断更新每个数字的出现个数，同时不断算 答案并且更新。
建议看这个学一下再
IOI 2013 wombats
假设是朝右朝下吧，不是很影响 对于 R 这一维建立线段树
决策是具有单调性的，路径有交叉可以通过调整变短
如果结束点从上往下走，那么中转点必然也是从上往下走的
复杂度是$O(c^2logclogr)$
建议看这个
IOI 2014 holiday
首先，肯定不会反复横跳
然后，结论就是$r$关于$l$是决策单调的。
不太会证，这里引用下钟神的证明：
设某个区间$[l,r]$的答案为$w(l,r)$。
考虑反证，设$l$的最优右端点为$r$，$l+1$的最优右端点为$r’$，且$r’ < r$。
那么我们有：
两式相加得到
即
显然是不成立的，因为上述式子的意义实际上是将$(r’,r]$的元素加入$[l,r’]$或者$[l+1,r’]$，带来的额外的贡献。由于加入的元素是相同的，而$[l,r’]$它可以去玩的天数更少，所以
WQS 二分
也就是常说的凸优化
这个东西有关的证明我是都不会的，往往看到$O(nk)$过不去十有八九就是凸的了。
Tree
我们考虑给所有白色边加权，通过调权值可以让最优策略的白色边个数变化。
通过二分调整权值使得最优策略正好需要need个白边
什么情况这样二分正确呢？如果代价关于个数的图像是凸的
若$f(x)$表示选择$x$个白边（上一个题）的代价
条件就是$f(x+1) - f(x) \geq f(x) - f(x-1)$
咋证明，我也不会，只会感性理解QAQ
邮局
如果权值满足四边形不等式，那 f 一定是凸的。
所以二分权值，然后用那个单调栈的方法dp一下
复杂度是$O(nlognlogv)$
—- 开始掉线 —-
因为轮廓线dp实在不会啊（
第二天讲了环版本
还是不会
Rikka with K-Match
没看太懂，后来再康康吧。。。wsl
林克卡特树
二分，搞个额外代价，虽然不会证明，但是它确实是凸的
一般$O(nk)$过不去都是凸的（确信）
一个经典题
操作A串（添加，删除，修改）使得AB循环同构
不循环重构
就是个$O(n^2)$dp
$dp[i][j]$可以由$dp[i-1][j-1] + c_M$,$dp[i-1][j] + c_A$,$dp[i][j-1]+c_d$转移得到
这个可以看成是平面图上的最段路
路径上的每个点当成决策点，对起点分治，找$0,\frac m 2$到$n , \frac m 2$的路径。
这个路径上半部分的点只对上面的起点有用，下半部分的点只对下半部分的起点有用
然后就可以分治下去做
这大概就是广义的决策单调性 ， 不仅可以用于dp
（这里也很晕）
循环同构复杂度是$n^2logn$的
图分治
没听到，起晚咕了，貌似只讲了几分钟，，，有时间回来补吧
树分治
点分治
最普通的树分治。每次选择重心向下分治就好了。不会超过$log$层的。
链分治
三度化
然后必然可以选择一条边，使得接下来剩下的两个树$size$最大是原来的$\frac 2 3$加一。
好处在于，链分治后你每次只需要merge两个子树的信息，比较好写。深度也是log的
点分治题目的几个做法
比如，路径长度不超过$k$的路径条数
容斥
每个点单独排序算，容斥减掉
这个题就是，任意选择两个点长度不超过$k$减去来自同一子树不超过$k$
可以分别sort一下再总sort，双指针解决问题
如果不能容斥 逐一加入
每加入一个子树，求这个子树中的$v$使得$dis[v] \leq k - dis[u]$
可以BIT维护
用哈夫曼树的方法，每次合并最小的两个儿子
假设合并复杂度是$O(S_i+S_j)$
这样一直合并最小的，复杂度也是对的 带log
一个位置的合并复杂度是 一个 log总复杂度两个log
问多少点对之间构成路径是合法括号序
点分治，
最终要满足的必然是$u$到$r$的路径只剩下了一些左括号了，$r$到$v$只剩下一些右括号了。
问距离为素数的点对（距离为 1 ~ n ） 的点对
还是考虑是否经过分治中心
每个子树写成生成函数$p_i$的形式，$a_k$表示有多少个深度为$k$的
要求的是$\displaystyle \sum_{i\neq j} p_ip_j$
可以$\frac{(\sum p_i)^2-\sum p_i^2}{2}$容斥做
树上背包
给定一棵树，每个位置都有容量和价值，选一个联通子树使得体积和小于等于$V$重量和最大。
如果确定了选根，那么你总是需要合并两个背包然后人就没了
先按照 DFS 序排序后，子树总是一段连续区间
$dp[i][j]$考虑$i … n$这段物品，考虑一个物品选了，在下个物品继续选择$dp[i+1][j-v_i] + w_i$
如果一个物品没选，必须把整个子树跳过$dp[r_i][j]$
这样可以处理根一定被选择的答案，复杂度是$O(nV)$
根不一定被选，所以套一层点分质就对了。
复杂度是$O(nVlog)$
一棵树，每个点还是有代价和权值，选择一些物品，使得它们不在树上相邻。
求出这样的东西的背包
$n \leq 100 , V \leq 10000$
复杂度是$n^2 V$
考虑点分，按照点分治选择根的顺序标号，考虑$dp[i][j][S]$前$i$个物品，容量和是$j$，前面每个物品选没选是$S$（集合）这样算法复杂度是$nV2^n$
但是实际上前一个子树不会影响后一个子树，所以我们不需要知道每个点是否被选只需要记录点分中心是否被选。所以$S$只需要记录这个点到根的路径是否被选，$S$是$2^{log}$，复杂度没问题。
HDU6556 可以写一下。
点分树
点分治过程中形成的树，可以方便处理带修改的问题。修改的处理往往是从一个点向上跳（只有 log 层）
BZOJ 3730
对于所有$x,r$求$\displaystyle \sum _{dis(v,x)\leq r} b_v$
点分，分$x$到$v$的路径是否经过中心讨论。
考虑跨过中心的话，
现在要求的其实是$dis(v,T) \leq r - d_x$的点 - 在$x$子树中$dis(v,T) \leq r-d_x$的点。
对于每个$T$记录小于等于$k$的权值和。
怎么加修改呢？我们对于每个点都仍然记录了小于等于$k$的权值和。我们可以用一个大小为 $O(size)$的BIT记录这个，这样小于等于$k$就是前缀查询。
如果一个点被修改了，到它的所有点分中心都要被修改。
这些点分中心分别单点改就好了。
Qtree 4 / zjoi Hide
边分治可能要简单一点，因为每次只用处理两个部分
先三度化，然后选择一个边切掉，考虑两个黑点是否经过分治边。
其实就是这个边两端的最远距离。分治的时候分别记录边两棵子树所有黑点到根的距离
由于支持点修改，可以每个分治中心搞个 multiset 维护
外部再开个multiset表示每个分治中心对答案的贡献。$nlog^2n$
其实有单log做法的
可以先把欧拉序写出来，然后$q$$p$的距离就是$dep[q]+dep[v]-2\min\{dep[r]\} ,q\leq r \leq p$
直径就是要加个$max$
所以就是$\max\{dep[p]+dep[q]-2dep[r]\},q\leq r\leq p$
所以其实就是要找给定欧拉序，整个序列要选择三个位置，第一、三个位置贡献是1，第二个是-2，使得权值尽量大。线段树记录一下$p$在这个区间，$pr$都在这个区间，$r$在这个区间…这些东西。然后这个是可以 pushup 的
给定一个树，每个点有权值$a_i$，修改$a_i$，查询$\min_u \sum a_i dis(i,u)$
每个点度数不超过20（其实没有貌似也可以做，三度化一下嘛）
当这个东西取到最小，$u$必然是重心。如果是重心每个子树的和都不会超过$\frac {\sum a_i} 2$。因为如果不是重心，我们明显可以往多于$\frac S 2$的儿子走，这样一定可以让答案变小。
所以要求的其实是一个带权重心。
单独求这个其实很简单，如果所有子树都不超过一半就是这个点，否则往多于一半的儿子走就好了。
建立点分树，我们递归下去后一个子树是这个递归下去的子树的大小，但是我们需要维护的是这个子树在全局意义下的大小。如果我们当前在$T_1$我们要进入$T_2$我们就把$T_1$的重量全部挂到$T_2$的某一个分支。就是把对应的子树的权值加$w$，做完了再减掉就好了。
CF 566C
给定i一棵树$\min_x \sum dis(i,x)^{1.5}$
$f(x) = x^{1.5}$是凸函数 加几次都是凸函数，所以$G(x) = \sum d(x,i)$也是凸函数
还是找一个点分治的重心，看它往哪边跳会变大。必然只有往一个方向走会变小，因为如果有两个方向走可以变小，那么一定不是凸函数。
如何找到往哪个方向会变小？这里做法是求导，假设 第$i$个子树的根是$rt_i$这个子树内所有点的导数的和是$p_i$那么往这个方面走是$\sum p_j - 2p_i$，需要找到唯一一个方向，使得导数是负数的方向走
具体看 这个 吧
动态点分治 紫荆花之恋
添加叶子，维护点分树的结构
点分树的结构是很容易变的啊（添加叶子时）
所以我们维护的不是严格的点分树，而是每个点的儿子要小于等于$\alpha n$的，$\alpha $一般取 0.8~0.9
这样整个树也是一个log级别的
但是我们一直往一边插入节点，明显会变得不平衡
所以如果某个子树不平衡了，dfs这个子树并且重构一边就好了，其实和替罪羊的pia操作一样
复杂度分析也是和替罪羊一样的
重量平衡树 带插入区间 kth
（从分治与分块自然过渡到数据结构？）
重量平衡树要做的事情是，一个点插入影响的子树只有$O(logn)$的（不管是期望，严格之类的）所以splay修改的子树大小是$O(n)$的。就是一个点插入后需要更新的个数是 log 的
只有这样可以方便的套其他树
重量平衡树： Treap，替罪羊
做这个大概就是替罪羊套 线段树
应用：有个序列，可以在log的复杂度插入，O1比较两个数哪个在前面
对于每个点我们维护一个区间，比如根节点是0,1，根的左儿子是$0,0.5$右儿子是$0.5,1$
这样的话直接插入可能导致一些问题，可能精度不够或者退化$n^2$
所以需要重量平衡树比如替罪羊的同构
分块
分块实质上可以看成一个$\sqrt n$叉树
引入：区间+区间求和
分块：大小 sqrt n 分成若干块 整段打标记，零散暴力
区间求和就一样
$O(m\sqrt n)$
区间+ 区间小于 x 的个数
还是先分块 对于整块+ 就打标记，零散块直接+
查询两头暴力 for ，块内维护了有序的序列，一个 log
块大小设$\sqrt{nlogn}$
区间 + 查询区间 kth
外面再套个二分。
直接做的话
查询，是$\frac n T log^2n + Tlogn$
修改，是$\frac n T + T$
直接做是$\sqrt n log^{1.5}$不太行
可以把$T logn$这部分优化成$T + logn$因为可以先拿零散块归并一下
这样就可以$T = \sqrt n logn$
根号平衡！
优化复杂度利器
-$O(1)$修改，$O(\sqrt n)$求和
直接分块做
-$O(\sqrt n)$修改，$O(1)$求和
每个块内部维护前缀和，维护整块前缀和
反正类似这个的问题都是可以根号平衡的
-$O(1)$插入$O(\sqrt n)$查询 kth
值域分块
查询 kth 貌似变成了一个找前缀和大于 k 的问题。遍历块即可。$O(\sqrt n)$
-$O(\sqrt n)$插入$O(1)$查询 kth
数字从小到大排序，每块大小都是$T$级别的
插入一个位置，对后面每个块都是前面插入一个，从后面pop一个
其实就是块状链表吧？
查询 kth 就直接查就好了。因为每个块大小固定
给定$n$个数，和$m$个函数，每个函数是$l_i,r_i$数的和
每次询问：
1 把第x个数字变成y
2 求 x…y 函数的和
把函数分块，维护每块函数的和，然后就是求两头额外函数的和。
预处理每个数字对一个块的贡献是多少
修改是$O(\sqrt n)$的。
用前面那个平衡的方法，是$O(m\sqrt n)$的
莫队
做那种可以快速支持插入删除，但是完全不能支持信息合并的问题
当然有些时候也不可以删除，这种情况是回滚莫队
引入：区间内所有数字出现次数的平方和
插入删除明显$O(1)$
做法是对所有询问分个块（按照$T$）
每块的询问按照左端点所在的块，右端点从左往右走
这样看起来复杂度就很$\sqrt n$
复杂度就是$O( n\sqrt m )$我也不知道为什么。
块大小$O(\frac {n}{\sqrt m})$
一个优化
奇数块从小到达，偶数从大到小
右端点是来回跳的，快一些。
（科学研究表明）最快 的 块大小$\frac n {\sqrt{\frac 2 3 m}}$
查询区间值在$[a,b]$内的不同数个数
跑莫队维护树状数组，复杂度是带log的根号
我们可以运用添加$O(1)$查询$O(\sqrt n)$的根号平衡，复杂度是一个根号。
BZOJ 3920
给定一个序列，查询区间中出现次数$k_1$小的数里面$k_2$小的数
先离散化，比如 $x$出现了$cnt_x$次，把$(1,x),(2,x),…,(c,x)$离散化，每次加一个数进来，就是加一个$(c+1,x)$进来。
查询就是利用前面那个修改$O(1)$查询$O(\sqrt n )$kth 的根号平衡
LOJ 2874
一个数的权值是它出现的次数 * 数值大小，查询区间中最大的权值
对于所有数字 $x$你就把$x , 2x , 3x, … ,cnt x$离散化
然后问题就变成了你要支持维护最大值的莫队
按照权值分块找最大值就可以了。
区间逆序对
最简单的做法：莫队树状数组，带 log
如何去掉log？
我们要做$O(n\sqrt m )$次查询$l , r$小于等于$x$有多少个
如果可以离线，这个就可以做
就是我们可以块状树的方法去做，但是这个查询的区间是在改变的
最暴力的方法是把那个分块结构可持久化
每次做就把修改过的块复制一遍，再把所有块之间的前缀和给复制一遍
但是这个方法也不优秀 常数很大空间也不优秀
因为数组开大了cache读取也很慢
所以有另一种方法——
二次离线莫队
[a,b] [c,d]表示$x \in [a,b], y\in [c,d] , a_x > a_y$的数量
从$l , r$移动到$l , r’$，增加量是
$\sum_{i=r}^{r’} [l,i-1][i,i]$
把$l,i-1$拆成两个前缀的-
增量是$\sum_{i=r+1}^{r’} [1,i-1][i,i] - [1,l-1][i,i]$
左边的东西只跟$i$有关，右边那个加起来是$[1,l-1][r+1,r’]$
现在我们相当于有了$m$个这样的询问
对于这个东西我们再次做一次离线
按照$l$排序，一个一个数字加进去，然后我们就有询问，就可以 for 一下$r+1,r’$来做
这就是第二次离线
很巧妙 啊QAQ
树上莫队
解决一些树上查询的问题
比如一条路径有多少种不同的颜色
怎样写比较简单呢？
用欧拉序，把每个东西进栈写一次出栈写一次
对于 A 点 和 B 点，找到它们在序列中第一次出现的位置，然后把它们第一次出现的位置之间的东西拿出来
把拿出来的数出现了两次的东西都去掉，再把端点和 LCA 胡上去
现在得到的就是这条路径上的东西
这个东西复杂度就是序列莫队（其实就是序列莫队）
就是一个把树上问题转移到链上的做法
带修莫队
莫队上面会有一些修改操作
我们把时间当成一维，两个修改的距离就是三个维度都移动，复杂度是$O(n^{\frac 5 3})$
块大小大概是$n^{\frac 2 3}$
先按照$l$所在块，在用$r$所在块，再用$t$排序
最坏复杂度$n^\frac 5 3$
证明：我不会
Codechef QCHEF
求区间最大的$|x-y|$使得$a_x = a_y$
回滚莫队，就是这种不好删除比较好插入的题。我不太会，上课过的有点快，先咕一会
CF 765 F （由于块太毒瘤突然插入的一个线段树题）
查询区间绝对值差的最小值
$l , r$间的$|a_i-b_i|$的最小值
扫右端点维护左端点的答案
分大于$a_r$和小于讨论
找到靠后第一个比$a_r$大的东西，可以用$a_j - a_r$更新所有$1 \leq l \leq j$的答案
然后找到一个小于等于这两个数平均数的元素
因为如果比这两个平均数大，$a_j - a_k$来得更小，$a_r$不会影响答案
同理一直这样找小于等于平均数的数字
这个可以对值域开一个线段树，每个权值记录它最后出现的位置，每次要查询的是$a_i$前面第一个比$a_i$大的，就是$a_i+1,+\infin$最大的值，然后就变成查询$a_i+1,\frac{a_i+a_j}{2}$的最靠后来更新。复杂度是$O(nlognlogv)$
据说有单log或者双log带修不会
经典问题
点权+，查询$x$相邻的点权和
按照度数 是否大于$\sqrt m$来分类做。
每个点记录下它的小邻居的和，修改小点直接给出去的边修改。
修改大点，直接修改
查询 查大点就好了
复杂度是 根号
树，点权，多次查询，每次给 x y k 求从 x 开始每次跳k个节点到 y 所经过节点的和
按照$k$与根号关系，
大于根号就直接跳，我们可以树剖一下，对于每个链我们记录一下，如果在一个重链上跳是不会有log的 ， 长链剖分就没log了
或者我们对于每个点记录它的一级，二级，…sqrt 级祖先，和sqrt , 2sqrt…级祖先
小于根号就是求 x 到 y 路上 深度 % k 为 r 的点权和
x 到根的 深度膜k为r的点权和 dfs的时候拿个数组记录一下膜k为r的点权和为多少
（其实对k很大也可以离线来做的）
复杂度是可以线性的
YNOI 2015 此时此刻的光辉
查询区间乘积的约数个数
暴力莫队，对每个因子记下出现次数，会TLE
本质不同的因子个数不是log个，是 log/loglog 但是还是T了
每个数的大于$v^{\frac 1 3}$的质因数个数只有2个，小于等于$v^\frac 1 3$的质数只有$v^ \frac 1 3log$
v = 1e9小于1000的质因数个数只有168个
维护感觉类似寿司晚宴
树分块
COT 2
树，点权，强制在线，查链颜色数
随机打$\sqrt n$ 个点，可以认为一个点到它上一个被选中的点的距离期望是$\sqrt n$的。
或者用深度是$\sqrt n$的倍数并且它往下的深度是大于根号的点
这样选择可以保证每个点往上$2\sqrt n$必然可以碰到关键点。
我们先预处理出关键点两两间的答案
预处理是从每个关键点dfs就知道了关键点两两答案。
现在就是看某个颜色从某个点到根的出现次数
这个比较暴力好想的做法是主席树，记录某个颜色的出现次数，复杂度是一个log
但是其实可以套用之前的分块结构，修改$n^\frac 1 2$查询$O(1)$的块状树，可持久化一下，这样就可以做到$O(1)$了虽然空间有点菜是$n\sqrt n$