(Preface)
一种高端科技，在NOI2020Day1T3爆炸之后，不会(A)部分分（裸·区间逆序对）的余下定决心要好好学习根号算法。
二次离线莫队听名字就是个非常高级的东西，而且虽说是二次离线，但它的复杂度仍旧是(O(nsqrt n))，非常神奇。
应用范围
一般用于移动左右端点时复杂度较大的莫队。
例如区间逆序对，它有一个非常显然的莫队+树状数组的(O(nsqrt nlogn))做法，原因就是每次移动端点时要在树状数组上询问。
而二次离线莫队可以完美解决这个问题。
以区间逆序对问题为例
假设当前左右端点为(L,R)，现要将右端点向右移一位。
考虑这次移动之后，答案的变化值就是([L,R])中大于(a_{R+1})的数的个数。
这东西可以拆成两个：([1,R])中大于(a_{R+1})的数的个数减去([1,L-1])中大于(a_{R+1})的数的个数。
其中前面那个东西显然可以树状数组(O(nlogn))预处理。
而后面这个东西，我们可以对于每个位置开一个(vector)，然后把(R+1)连同当前询问的编号一同扔到(L-1)的(vector)中。
根据莫队的复杂度证明，我们一共会移动端点(O(nsqrt n))次，这样的内存可能会有点大。
然而我们发现，假设一个询问需要我们把(R)向右移到(R')，移动过程中(L)是保持不动的，因此实际上我们可以直接把([R+1,R'])整个区间连同询问编号一起扔到(L-1)的(vector)中。这样一来内存就是(O(n))级别的了。
把移动区间扔到(L-1)的(vector)中的过程，就是第二次离线。
然后我们只要从左到右枚举每一个位置，处理该位置(vector)中的询问。
注意虽然我们存的是区间，但询问时依旧要枚举区间中的每一个数一个个询问，询问次数依旧是(O(nsqrt n))的。
又由于我们只会枚举(1sim n)这(n)个位置，因此可以考虑适当增加修改的复杂度以实现(O(1))询问。
于是就想到(O(nsqrt n))修改、(O(1))询问的分块。
这样就彻底解决了整个问题。
具体实现过程（伪代码？）
具体实现中，由于左端点移动和右端点移动答案变化值询问范围相反，因此很多东西都要开两个。
- 读入数据并进行一些简单处理（例如离散化）。
- 预处理： 设(t1_i,t2_i)分别表示(1sim i-1)中大于/小于(i)的数的个数，则用树状数组预处理出它俩的前缀和(s1_i,s2_i)。（(t1_i,t2_i)无需存储）
- 第一次离线： 给询问排序，进行莫队。（(g1[x],g2[x])为每个位置的两个(vector)，四元组表示询问左/右端点、询问编号以及对答案贡献的符号）
- (R<r_i)：往(g1[L-1])中扔入((R+1,r_i,pos_i,-1))，(ans[pos_i])加上(s1_{r_i}-s1_R)，然后令(R=r_i)。
- (L>l_i)：往(g2[R])中扔入((l_i,L-1,pos_i,1))，(ans[pos_i])减去(s2_{L-1}-s2_{l_i-1})，然后令(L=l_i)。
- (R>r_i)：往(g1[L-1])中扔入((R_i+1,R,pos_i,1))，(ans[pos_i])减去(s1_R-s1_{r_i})，然后令(R=r_i)。
- (L<l_i)：往(g2[R])中扔入((L,l_i-1,pos_i,-1))，(ans[pos_i])加上(s2_{l_i-1}-s2_{L-1})，然后令(L=l_i)。
- 第二次离线： 枚举每一个位置，处理(vector)中的询问。
- (O(sqrt n))加入(a_i)的贡献。
- 枚举(g1)中的元素((l,r,pos,op))，枚举(xin[l,r])，给(ans[pos])加上(op imes Q1(a_x+1))（(Q1(v))返回大于等于(v)的数的个数）。
- 枚举(g2)中的元素((l,r,pos,op))，枚举(xin[l,r])，给(ans[pos])加上(op imes Q2(a_x-1))（(Q2(v))返回小于等于(v)的数的个数）。
- 最后，给答案做个前缀和（因为我们求出的只是答案变化值），然后输出。
时间复杂度分析
预处理（树状数组）：(O(nlogn))
第一次离线（莫队）：(O(n))（因为此时我们没必要再一点一点移动端点，直接一步到位就可以了）
第二次离线（分块）：(O(nsqrt n))（修改单次复杂度(O(sqrt n))，次数(O(n))；询问单次复杂度(O(1))，次数(O(nsqrt n))）
总复杂度：(O(nsqrt n))
（如有不对请指出~~~）
(Postscript)
毒瘤lxl的题目让我感受到深深的恶意，果然NOI这种东西还不是余现在的水平能够挑战的。。。