树状数组

基础

例题1

给定n个点(n 1e5),求矩形范围内的点的个数。可离线。

解法

二维偏序板子题,将询问加入序列,先按一维排序,树状数组维护偏序。

例题2

给定n个值($n 1e5,a_i \pm 1e9$),可任意改变值的正负,求最少逆序对。

解法

按照绝对值分类讨论,对于$\left|a_j\right|\ge\left|a_i\right|$,无论怎么改变正负都不对逆序对数产生影响;对于$\left|a_j\right|\ge\left|a_i\right|$,若$a_i$取负则增加$\sum[j<i,\left|a_j\right|>\left|a_i\right|]$,否则增加$\sum[j>i,\left|a_j\right|>\left|a_i\right|]$。

线段树

基础

例题1

给定一个长为n($n 1e5$)的环形序列A,有q次修改操作,求连续最大子段和。

解法

容易考虑到拆环为链,但不容易保证截取出的链长$\le n$,所以转换为总和-中间连续最小子段和和连续最大子段和取max

例题2

[SDOI2016]游戏

李超线段树

解法

考虑到直线交点只会出现在[左/右]一个区间,修改时若整个区间内无交点直接抛弃较劣的一条,否则分别下放标记,若交点在左子区间将较优的直接赋给该区间,较劣的下传给左子区间,依次类推。

可并堆&线段树合并

例题

[APIO2012]派遣

解法1

用可并堆。已经做过了,略。

解法2

用线段树合并。复杂度$\Omega(nlogn)$

平衡树

启发式合并

有脑子地暴力就好(小的往大的上面暴力合并)。

例题1

给定三个长n($n \le 5e6$)的排列ABC,统计有多少对(i,j)满足$A_i<A_j,B_i<B_j,C_i<C_j$

解法

和三位偏序有一些区别,并且数据范围非常大。正解是使用容斥

设$F(i,j)=[A_i<A_j,B_i<B_j],G(i,j)=[B..,C..],H(i,j)=[C..,A..]$,观察发现若一对$i,j$同时满足F、G则一定也满足H,因此若计算$\sum F,\sum G,\sum H$,则一对合法的$i,j$产生的贡献为3,不合法的$i,j$产生的贡献一定为1。

因此设答案为$Ans$,有$\sum F+\sum G+\sum H=Ans\cdot3+\sum[illegal]$,且有$Ans=\binom{n}{2}-\sum[illegal]$。变形得到$Ans=\frac{1}{2}(\sum F+\sum G+\sum H-\binom{n}{2})$,即可在$O(nlogn)$复杂度内求解。

keyboard_arrow_up