CDQ三维支配统计

先让第一维变成“在前面” ​

把更新和查询合在一起，按第一维升序排序；第一维相同时，所有更新排在所有查询之前，同类再按原编号排列。于是对一对更新u和查询v，u在v前面当且仅当xᵤ≤Xᵥ。这里的相等规则决定闭区间语义，不能随意交给不稳定排序。

按这个初始顺序将记录均分成左右两半。合法对只有三类：两端都在左半、都在右半、更新在左而查询在右。前两类交给孩子，当前结点只处理第三类。更新在右、查询在左时第一维条件已经不成立，不应计入。

每一对只有一个负责结点 ​

固定一对u、v，从整段向下寻找：只要它们还在同一半，就进入那个孩子；最终有唯一一个结点第一次把二者分开。因为u在前，必是u在左、v在右。更低结点不能同时含二者，更高结点又把它们放在同一半，因此这对恰在该结点被检查一次。

分治边界指的是初始第一维顺序中的记录身份。孩子返回时可以按第二维重新排列自己内部的记录，但不能让记录跨越原左右集合。这区分了“为了扫描改变枚举次序”和“改变分治负责哪些对”。

跨半贡献变成一维动态前缀和 ​

两个孩子分别返回按y排序的列表。按Y从小到大遍历右半查询，同时推进左半列表，把yᵤ≤当前Y的左半更新加入临时结构；左半查询和右半更新在这一步不产生贡献。这个单向推进是扫描线方法理路扫描线范式Sweep-line paradigm · Plane sweep按事件推进一条虚拟直线，并用动态有序状态维护当前横截面组合关系的计算几何范式。在坐标上的应用。

只收集更新中出现的z，排序去重得到z₀<…<zσ₋₁。用树状数组理路Fenwick 树Fenwick tree · Binary indexed tree用二进制最低位分解维护动态前缀聚合，支持单点更新与前缀查询的对数时间数据结构。保存各坐标当前加入的权重和。查询阈值Z不必出现在更新坐标中：求有多少个压缩坐标≤Z，即 bisect_right(zs,Z)，再查询这么长的前缀。

扫描到v时，树中恰是当前结点左半且y≤Yᵥ的更新；这些更新又已满足第一维条件。第三维前缀只保留z≤Zᵥ，所以读出的正好是该结点负责的贡献。把它加到v的累计答案，所有结点的唯一归属证明便给出完整正确性。

离开前撤销本轮加入的权重 ​

一次跨半扫描结束后，逐个对本轮实际加入的更新执行相反权重−w。树状数组恢复全零，再供下一个结点使用。负权同样可撤销：加入−3，离开时加回3。

不能在每个递归结点重新分配或清零长度σ的数组；有O(N)个结点时，这会额外产生O(Nσ)工作。附件只有一棵共享树，以本轮加入列表精确减回。记录不是任意版本快照，不需要持久化树或回滚并查集。

相同坐标不会互相吞掉 ​

取四个更新：u₀=(0,1,2,+3)、u₁=(0,1,2,−1)、u₂=(1,0,2,+5)、u₃=(0,2,1,+7)。查询v₀=(0,1,2)只包含u₀、u₁，答案2；v₁=(1,2,2)包含全部四项，答案14。

初始顺序为u₀,u₁,u₃,v₀,u₂,v₁，根分成前三条和后三条。根扫描给v₀贡献2、给v₁贡献9；右子树中u₂再给v₁贡献5。两个答案是2和9+5，而不是把“同一点”去重后只留+3或−1。

若第一维相同时把v₀放在更新前面，u₀、u₁会被漏掉；若第二维用严格小于推进，也会漏掉y=1的这两条；若第三维用lower bound直接查前缀，则会排除z=2。三处都必须与≤的定义一致。

点赋值怎样化为正负事件 ​

对长度n的数组，将位置i编码为第二维i+1。初始A[i]在时间0产生更新(0,i+1,A[i],+1)。时间t把位置i从旧值a赋成b，就产生(t,i+1,a,−1)和(t,i+1,b,+1)。其余位置没有事件。

定义H(t,p,k)为三维阈值(t,p,k)的答案。每个位置的初始+1与后续旧值−1、新值+1相消后，恰留下时刻t当前值的一份。因此区间计数为

注意减的是l，不是l−1：位置编码从i变成了i+1。l=r时两个查询相同，差为零。相同值的重复赋值产生一负一正，也会正确抵消。附件给每条命令独立时间，因而查询反映它之前全部赋值；若外部允许同一日期混合多条记录，须约定日期内更新先于查询。

有未来输入，不等于可以预知它 ​

若下一条查询的真实坐标必须用前次答案解码，尚未解码的记录不能提前排序。这里要求的是实际更新和实际查询全部已知，而非文件里仅有一串加密参数。范围树理路范围树range tree以主坐标搜索树和节点关联目录支持固定维正交范围查询。适合另一类接口：先建立静态点集目录，再接受未来范围请求；本页不会返回这种索引。

没有更新时，所有答案为零；没有查询时，结果为空。坐标可为负且跨度任意大，压缩空间按出现的坐标数计算，不按最大坐标值开数组。

为什么只有两个对数 ​

第一维排序和第三维压缩耗O(N log(N+1))。分治有O(log(N+1))层；每层所有子段的记录数合为N。一个结点的跨半扫描只推进左右列表一次，每次更新加入、撤销及每个前缀查询为O(1+log(σ+1))；随后线性归并两个y有序列表。

因此每层O(N log(N+1))，总时间O(1+N log²(N+1))。在每个结点重新比较排序y虽未必改变本例的大O上界，却会增加不必要工作；返回有序列表直接显示扫描与归并的来源。第三维前缀边界在预处理时计算一次。

递归返回列表后不保存整棵历史。沿当前调用路径，未处理子段、已完成兄弟列表与当前合并缓冲的长度按n、n/2、n/4…计，总量O(N)；共享树、坐标表、答案也为O(N)，栈深O(log(N+1))。保存所有层的完整轨迹会另占O(N log(N+1))，不属于核心线性空间。

整数坐标、权重及中间总和须装入常数个机器字，以上为RAM成本。任意精度整数可保证不会溢出，但比较和加减的位成本应另计。附件的 audit=True 逐结点扫描整棵树检查归零，是故意较慢的测试模式；生产界针对关闭该检查的核心。

把统计和动态规划的依赖区别开 ​

本页每条更新的权重从输入就已确定，故可以先递归两半，再计算左对右贡献。CDQ也能维护动态规划决策，但若右侧更新值依赖左侧新算出的答案，就必须先完成左半、传播影响，再求右半；不能机械照搬本页顺序。陈丹琦原文的Cash与Mokia两例正好展示这两种不同依赖。[1]

在批量查询终结任务中，将同一赋值轨迹产生的14条更新与8条前缀查询交给本算法，再与排序分块理路平方根分解Square-root decomposition · Sqrt decomposition · 根号分解将数组分成可维护的连续块，在两端直接扫描、中间整块查询，并按摘要能力核算更新与块长。的在线结果核对。两边都必须按查询编号给出[4,2,5,0]，负事件是模型的一部分，不能因为“计数不应为负”而丢弃。