限定范围

1. 初始先排序的实现方式。
2. 从小到大处理不会破坏分界限。

本篇可能只是本苣蒻没有意识到所导致的，但是或许对于其他的初学者，估计也有可能会卡在这里。

问题描述

首先，可以发现正解的实现方式需要向寻找下标小的那一边，右要寻找下标大的一边。

对于要被删除的点，这样的计算方式是显然正确的，但是对于从来都没有被删除的的点，题解中的处理方式是赋值为$m + 1$。

此时就出现了问题，若此时还对下标大的计数，又对下标小的计数，那么是否会出现重复统计？

如果此时严谨的将其视为偏序的问题，统计(t为删除时间)$t_j \ge t_i \land idx_j < idx_j \land a_j > a_i$和$t_j \ge t_i \land idx_j > idx_j \land a_j < a_i$的个数，对于$idx_i<idx_j$,$i$统计一式可能会统计$j$,$j$统计二式可能会统计i，所以每个都会被算两次。

验证

上述问题很容易构造数据，题解里也有非CDQ的方法，经过以下程序生成的数据，并没有卡掉CDQ的代码：

import random

p = [i for i in range(1,(10 ** 5)+1)]
random.shuffle(p)

with open("data.in", "w") as f:
    print(10 ** 5, 5 * 10 ** 4,file=f)
    for i in p:
        print(i,file=f)
    random.shuffle(p)
    for i in range(5*(10**4)):
        print(p[i],file=f)

那么可以说明，CDQ的某些实现方式，无形中避免了这一问题。

可能的解释方式

纯作者的思考，若有错误欢迎大佬指正。

适用范围里指出，首先进行了排序，然后。

//主程序:
// 排序 -------
solve(1,n);
// solve函数中
solve(1,mid);
solve(mid+1,r);
// 再次排序----

可以观察到，程序直接递归到了底部，然而后面的再次排序也只会在自己的$[l，r]$范围内。

然后依照CDQ的思想，左边的向右边的算贡献。

假设 A 对 B 做了贡献，那么 A 一定在 B 的左边的区间，且仅算一次贡献，然后 B 于 A 合并为一个区间，不再计算内部的贡献。

所以，CDQ分治可能对于一个点对，只会计算一次贡献，即使不断的改变统计方式，统计反复统计，对于每一个点对，也会出现每队可能相互统计的点对，只会被统计一次

应用

CDQ实现的细节