上一期
中场休息
我们来讲讲一些整体二分的细节。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1.答案的归属。设当前 midmidmid 检查出来的值 ttt 等于所询问的 kkk 值，此时这个询问是应当分到左组还是分到右组呢？
答：左组。左组答案区间为 [l,mid][l,mid][l,mid] ，右组答案区间为 (mid,r](mid,r](mid,r],如果答案刚好为 midmidmid 分到左组才能得到正确答案。
2.整体二分的小优化
注意到当操作集合中不包含询问操作时，该集合无效。因此可以判断左组和右组是否有询问，有再进行递归。使用这个技巧的代码将在 P4602 给出。
以下是一些使用该技巧的测试结果。
所用时长(最长/总数） P4137 P1527 P3332 P4602 普通写法 197ms/2.08s197ms/2.08s197ms/2.08s 247ms/2.77s247ms/2.77s247ms/2.77s 273ms/1.8s273ms/1.8s273ms/1.8s 176ms/1.65s176ms/1.65s176ms/1.65s 优化写法 149ms/1.57s149ms/1.57s149ms/1.57s 243ms/2.73s243ms/2.73s243ms/2.73s 269ms/1.69s269ms/1.69s269ms/1.69s
164ms/1.54s164ms/1.54s164ms/1.54s
可以看出这个优化还是有一定用处的。
这个优化对于大部分整体二分来说最多优化 O(NlogN)O(NlogN)O(NlogN),因为它优化的是插入操作，一般的整体二分中插入会进行 N 次，复杂度为 O(NlogN)O(NlogN)O(NlogN) ，为该优化的上限。
P4602为特殊情况，见后文。
第二部分 CDQCDQCDQ 分治
本篇仅讲述 CDQCDQCDQ 分治用于处理点对的应用，更多应用详见 OI-wiki
老规矩，if 你看完全篇还不会，考虑此视频
CDQCDQCDQ 分治的经典应用是三维偏序。
先考虑二维偏序，有两种解法：
1.归并排序求解。归并时先被分进主序列的左组元素都对右组该元素的逆序对产生贡献。可以上网寻找资料。
2.树状数组（线段树）求解。由于二维偏序通常是给定若干元素，按元素位置进行贡献，因此无须去重。按位置从左到右依个将元素值加入树状数组，在加入一个元素前先计算它的值~最大值的下标的和，即为在它之前又比它大的元素数量； 也可倒序插入，插入前计算1~该元素的值。
CDQCDQCDQ 分治求解的前置知识是第二种二位偏序解法。
题目描述
有 nnn 个元素，第 iii 个元素有 ai,bi,cia_i,b_i,c_iai ,bi ,ci 三个属性，设 f(i)f(i)f(i) 表示满足 aj≤aia_j \leq a_iaj ≤ai 且 bj≤bib_j \leq b_ibj ≤bi 且 cj≤cic_j \leq c_icj ≤ci 且 j≠ij\ne ij=i 的 jjj 的数量。
对于所有 d∈[0,n)d \in [0, n)d∈[0,n) ，求 f(i)=df(i)=df(i)=d 的数量。
~~ K-D 树和二维树状数组套值域树状数组一眼题~~
设三个属性分别为 aaa , bbb 和 ccc
CDQCDQCDQ 分治的做法是将数组分为两组，确保左组无法从右组获得贡献，右组可以从左组获得贡献。将这个性质定义为性质 A，体现为左组的某个属性小于等于右组的该属性。
先将所有元素按 aaa 从小到大排序，这样无论如何分组左边元素的 aaa 一定比右边的元素的 aaa 小，确保符合性质 A。然后进行分治： CDQCDQCDQ 分治是正常写法，先求解子问题再求解当前主问题，因此先分治；在每次递归结尾将 [l,r][l,r][l,r] 元素的 bbb 从小到大进行排序，由于已对 aaa 进行了排序，所以无论对该区间的元素怎样重排，**不难注意到它左边的所有元素的 aaa 都小于它的任意一个元素的 aaa ；它右边所有元素的 aaa 都大于它任意元素的 aaa **.处理 [l,r][l,r][l,r] 时，可得 [l,mid][l,mid][l,mid]
中的所有 a≤[mid+1,r]a\leq[mid+1,r]a≤[mid+1,r] 中的所有 aaa, 并且这两个子区间内的 bbb 保持有序。
接下来采用双指针的做法，如果左组当前元素的 bbb 小于右组当前元素的 bbb ，那么将右组指针后移，寻找更大的 bbb; 当目前右组元素的 bbb 大于左组当前元素的 bbb 时，持续将左组指针后移并将左组元素的 ccc 值插入树状数组直到 bbb 小于左组当前元素的 bbb.注意到此时左组当前元素的前驱和右组当前元素的 aaa 和 bbb 都符合性质 A，由于左组在之前（即当前元素前驱的左边）的元素 aaa 依旧比右组的 aaa 小，并且它们的 bbb 经过排序，一定比左组当前元素的 bbb 小。可以得出左组第一个到当前元素前驱的所有元素 aaa 和 bbb 都符合性质
A,使用树状数组的方式将左组所有 ccc 符合性质A的元素统计答案（这时所有 a、ba、ba、b 小于该元素的元素都将 ccc 值插入，这时统计1~该元素 ccc 值可以得到三者都比其小的左组所有元素数）。左右指针都推完后结束该区间计算，记得将所有元素按照 bbb 排序。请对照代码理解。
注意：以上思路其实有错误。你能找出来吗（朵拉音）
BYD ACGO 的 Markdown 为什么不兼容 HTML
错误：当 aaa 相等时， bbb 和 ccc 处于乱序，有可能将较小的 b、cb、cb、c 值分到较大的元素的右边，导致它们无法被这些较大的元素统计。学过超难超简单的结构体排序的你想到可以在 aaa 相同时按 bbb 排，然后 bbb 相同随便乱排（或者直接不排，会默认左参数小于右参数），这样你就能 AC 啦。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
AC 记录：
没有。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
哪里 AC 了，什么地方满足性质 A 了，你把三个属性都相同的元素当成什么了？
注意可以把三个属性相同的元素并成一个，树状数组插入时不加1而是加上这个元素的大小（就是共有多少元素相等然后并成这个元素），统计完将所有元素的答案加上大小再减去一（因为与其相等的所有其它元素都有贡献）即可。
Code:Code:Code:
AC 是 AC 了，排序在哪呢？
没错，双指针时顺手进行归并排序了
当然后面你就会见到我 sort 的写法因为归并有点不省事
依旧分享本题写法：
CDQCDQCDQ 分治，O(NlogNlogV)O(NlogNlogV)O(NlogNlogV)(离散化 O(Nlog2N)O(Nlog^2N)O(Nlog2N))；
整体二分（是的，居然是整体二分）O(NlogNlogV)O(NlogNlogV)O(NlogNlogV)(离散化 O(Nlog2N)O(Nlog^2N)O(Nlog2N))；
树套树 O(NlogN)O(NlogN)O(NlogN)；
K−DK-DK−D 树 O(NN)O(N\sqrt N)O(NN )；
分块 O(NN)O(N\sqrt N)O(NN )；
莫队 O(NN)O(N\sqrt N)O(NN )
二进制分组套小波矩阵 O((N+M)log2N)O((N+M)log^2N)O((N+M)log2N)
bitset, O(N2w)O(\frac{N^2}{w})O(wN2 )
注意！CDQCDQCDQ 分治的重要细节！虽然可能没人错，但是在所有右组遍历完后还是要把左组操作进行，因为后面清空 BIT（ST） 要全部抵消
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
接下来回到上一期开头的问题：动态逆序对
请自行读题。
读题之后容易发现最后一个输入没用
可以发现每次输出的答案后一个都比前一个小
看似是废话，那我们思考一下小了多少呢？
很明显是删除元素对答案的负贡献。每个答案都多计算一个元素的负贡献，可以考虑用类似前缀和的方法。先计算原序列总贡献，再递推每个删除元素的负贡献。
问题转化为：如何寻找负贡献？
先对代码进行简化，不需要去重，并考虑用sort直接实现。接下来可以将元素被删时间TimeTimeTime看作第三维的属性，注意到对于删除操作 iii,其负贡献的倒数为序列中满足 Timei<Timej,Time_i < Time_j,Timei <Timej , Vali<Valj,Val_i<Val_j,Vali <Valj , Posi>PosjPos_i>Pos_jPosi >Posj 或Timei<Timej,Time_i<Time_j,Timei <Timej , Vali>Valj,Val_i>Val_j,Vali >Valj , Posi<PosjPos_i<Pos_jPosi
<Posj 的元素个数。将其转化为三维偏序问题，进行答案运算时不考虑 TimeTimeTime,将序列从左到右遍历统计第一种贡献，再倒序处理第二种贡献。删除时像整体二分，用-1抵消插入操作；在计算贡献时乘上自己的 op ，确保插入操作统计正贡献、删除操作统计负贡献。本题有一定思考难度，请自行理解。
注意到求的是逆序对数量的总和，再看看数据量，不开 long long 见祖宗
Code:Code:Code:
所有解法：
CDQCDQCDQ 分治 O(Nlog2N)O(Nlog^2N)O(Nlog2N)
树状数组套主席树 O(Nlog2N)O(Nlog^2N)O(Nlog2N)
分块 O(NN)O(N\sqrt N)O(NN )
线段树套平衡树 O(NlogN+Mlog2N)O(NlogN+Mlog^2N)O(NlogN+Mlog2N)（甚至题解还有线段树套朴素BST）
K−DK-DK−D 树 O(NN)O(N\sqrt N)O(NN )
第三部分（部分）拓展问题
来点饮料怎么样？
毒瘤例题1：经典牢题 P4602 [CTSC2018] 混合果汁
也是做出 CTSC 了（虽然难度是紫）
自行观看题面！
本贴将会讲解两种解法。
没错，主席树
前排提醒：这只是主席树的一种做法
步骤：
1.一眼二分法。比答案小的所有美味度都能符合要求，比答案大的美味度不能，符合单调性。
2.考虑进行一次询问。每次 check 应尽量取美味度大于 midmidmid 、单价最小的果汁，取完体积再判断价格是否符合标准。可以建立值域线段树，以单价为下标，维护区间体积和与区间花费和（将区间所有果汁买下的花费），在值域线段树上进行线段树二分，可用体积小于等于左子树则向左递归，大于则更新可用体积并向右递归，最后返回消费和。如何维护美味值大于等于 midmidmid 的约束条件？注意到每次只有美味值在区间 [mid,maxn][mid,maxn][mid,maxn]
的元素可用，形成一个后缀关系。将美味值从大到小排列，将后缀关系转化为前缀关系，只考虑前缀的所有元素，明显可用主席树维护。具体编码时先从大到小排序美味度，然后建立主席树，二分某种果汁之前的所有果汁是否可用（而不用对美味度值域建树），再按上述步骤二分。注意到每次 check 复杂度为 O(logN)O(logN)O(logN) ,一次二分答案为 O(log2N)O(log^2N)O(log2N).推广到多次询问，可以用整体二分直接在线对每一个询问回答即可。总复杂度 O(Nlog2N)O(Nlog^2N)O(Nlog2N)。
哪有人两步推出解法的
Code:Code:Code:
没错，整体二分
注意你谷有很多复杂度假的整体二分，也就是 O(Nlog3N)O(Nlog^3N)O(Nlog3N) 甚至 O(N2log2N)O(N^2log^2N)O(N2log2N),请以我学习的这种思路和代码为参考，或者自己证明自己做法的复杂度。
貌似可以一次二分中再二分符合要求的价格，但是这样就会是二分套二分套整体二分，复杂度为 O(Nlog3N)O(Nlog^3N)O(Nlog3N).
1.与上述一样。
2.用整体二分套值域线段树。利用值域线段树二分，判断询问分到哪组。区别是不像主席树开一瞬千树一堆线段树，而是一次性使用，用的时候插元素进去，用完清空。但是如果每次都从 midmidmid 的果汁插到 rrr 的果汁复杂度会假，因此每次都复用原来的权值线段树 ，往左就插入更多元素，往右就删掉一些元素。如何证明复杂度？
注意到整体二分使用了递归，本质上是从值域的左到右执行操作，而不是同时进行，可以依此证明。
插入的用时分为从该轮递归跳到同一层递归和从该轮递归跳到更高层的递归。每层插入复杂度为左右层相加再加上左层最底部跳到右层最顶部的复杂度。计算得如下式：
t(N)=2t(N/2)+3N/4t(N)=2t(N/2)+3N/4t(N)=2t(N/2)+3N/4
计算次数为 O(NlogN)O(NlogN)O(NlogN) ,每次插入 O(logN)O(logN)O(logN) ,故总插入复杂度为 O(Nlog2N)O(Nlog^2N)O(Nlog2N),高于一般整体二分的 O(NlogN)O(NlogN)O(NlogN),但是加上询问为 O((N+Q)log2N)O((N+Q)log^2N)O((N+Q)log2N),依旧达标。使用小技巧优化只能优化少数极端情况或递归开销。
整体二分可能比主席树更难理解，但是……
Code!Code!Code!
时间复杂度：O(NlogNlogV)O(NlogNlogV)O(NlogNlogV)
本题其它解法：树状数组套树状数组 O(Nlog3N)O(Nlog^3N)O(Nlog3N)（解法最少的一集）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这期就到此为止了。也许有机会我还会把第三部分的例题补完。Say↑goodbye~
