Notes

有趣的想法 & 做题的灵感 & 解题的套路

2017 / 11

$n^3$ 的矩乘优化,如果发现转移矩乘是循环矩阵,可以把$n$次卷积优化成$1$次。只保留两个矩阵的第一行即可,然后对这两个数组卷积后的数组是结果矩阵的第一行,对于下一行是上一行的循环位移,题目「BZOJ 2510」。

图论上,如果边权均为正的最短路计数,可以先求出最短路,然后只保留可能是最短路的关键边。这时候可以把原图变成 DAG。如果询问是否存在某个最短路径可以穿过若干个点或者某几个点覆盖所有的最短路,可以从方案数方面考虑,即通过这些点的方案数的和是否等于总方案数,题目「LOJ 6252」,来自 CodePlus 11 月月赛。

切比雪夫距离转曼哈顿距离公式:$(x,y) \rightarrow (\frac{x + y}{2}, \frac{x - y}{2})$,证明可以通过分类讨论。如果要在一个棋盘上找到一个点到所有关键点的距离和最小,这个坐标是每个维度的中位数,题目「BZOJ 2735」。

矩阵求逆 一般常见于对于高斯消元,系数矩阵不变,答案向量发生改变时要多次求解。高斯消元可以理解为系数矩阵 $G$ 和变量向量 $A$ 以及常数向量 $B$ 所谓的高斯消元就是 $G \times A = B$ ,我们知道了$G$ 和 $B$,通过对矩阵的线性变换把$G$消成单位矩阵,同时作用于$B$,就得到了$A$,这个复杂度是$O(n^3)$的,当$B$多次改变时,我们仍然要再次进行高斯消元,这个时候就可以先求出$G$的逆矩阵$G^{-1}$,这个时候上式就变成了$A = G^{-1} \times B$,注意因为矩阵乘法不支持交换律,所以要注意消去的先后顺序。求逆矩阵的时候,我们只要对于当前的矩阵,将其消为单位矩阵,同时对一个单位矩阵施加相同的行列变化,就能得到他的逆矩阵。题目 「BZOJ 3640」。

拉格朗日乘数法,wiki 讲的很详细,不多说了,题目参考「BZOJ 2876」

路径异或问题的几个小结论:
从一个点出发的所有路径一定可以由若干个简单环和从起点到某个点的简单路径异或而成。所有的环也可以有若干个简单环异或而成。
题目,「BZOJ 2322」「BZOJ 2115」。

棋盘问题,首先考虑黑白染色,对于简单环相关的问题,要考虑到每个点的度数都为2,题目 「BZOJ 4261」。

同样的,对于一般图的匹配问题如果按照拆点跑匹配的处理,那么最后得到的一定是若干个环与链的匹配。

费用流每次增广得到的费用一定是递增的,所以可以利用这个性质二分,题目参考 「BZOJ 3691」。

2017 / 12

回滚莫队,即对于区间只增加不删除。考虑每个区间,把所有左端点位于一个块的看做同一类询问,然后一定能保证右端点递增。然后考虑右端点,我们每次从块的右端点出发,这样也可以做到只添加,复杂度不变。
题目是 「BZOJ 4241」

对于一些数据结构题来说,如果保证了操作是随机的,而且存在区间赋值的操作。那么可以考虑一种比较暴力的做法,即对于数值相同的段合并起来一起处理。这样的复杂度是$\log$级别的,题目是「Codeforces Round 449 Div1 D」。

多项式高斯引理,即任意一个多项式$f(x) = \sum a_i x^i$ 都可以表示成$f(x) = g(x) \prod (xb_i + c_i)$,其中$g(x)$对应了这个多项式为$0$时的所有无理数解,另一侧就对应了所有的有理数解。题目是「BZOJ 2742」

最小平方生成树,即每个边有两个边权,要求求出最小生成树,满足两个边权的和的乘积最小。我们考虑把一个方案的两个边权和映射到一个二维平面上,可以发现,最优的解一定在下凸包上,我们考虑分治求出这个凸包。首先我们分别只考虑两个边权中的一个求最小生成树,那么这个时候得到的一定是位于凸包边界上的两个点,然后对所有边与$le - ri$叉积,然后得到$mi$,分治下去即可,题目参考「BZOJ 2395」。

对于一些要求选出树上满足某些条件的路径,且要求路径数无交且最少的话。可以把问题转化到边上,即所有操作过的路径所对应的边集中,所有度数为奇数的点的数量即为最少的路径数,题目是 「CSAcademy #60 E Flip the Edges」

DAG 上的概率 DP,因为是分数形式,所以对于一些删边的问题可以套上分数规划和最小割那一套理论,题目是「BZOJ 4501」

数论相关的题,可以从$\mu$的取值的不同来考虑不同的计算方式,题目是「BZOJ 3512」

上下界网络流的最基本建图,是把一条边拆成三条,比如从$u \xrightarrow {(l,r)}v$,那么拆成$S\xrightarrow{l}v,u\xrightarrow{l}T,u\xrightarrow{r - l} v$,可以用流量平衡来证明正确性。

对于不同深度来说互相独立的树形 DP 题,可以考虑长链剖分,即每个点继承其深度最深的儿子的答案,然后和其他儿子进行合并。复杂度是$O(N)$的,可以用 deque 来实现避免手动进行内存分配,题目「arc 086 E」

删边最短路问题。可以考虑先随便抽出一条最短路。这个时候可以从删边的种类来分类讨论。如果不是抽出的最短路上的边,那答案显然不变,如果是最短路上的边,考虑预处理。对于所有不是最短路上的边$x\rightarrow y$,考虑找到$S$到$x$上的最后一个是最短路上的点$ss$,以及$y$到$T$上的第一个是最短路上的点$tt$,这个时候$ss\rightarrow tt$上的点都能被这条边覆盖。我们用线段树维护一下,取最小值即可,题目是「BZOJ 2725」。

动态图问题,可以考虑线段树分治然后用按秩合并的并查集来做。同时按秩合并的并查集也可以动态维护两点路径长度的奇偶性,题目是「BZOJ 4025」,这个题也可以用 LCT 做,按每条边删除时间,动态维护一个最大生成树即可。

字符串相关的博弈论问题,可以考虑把多个字符串建成 Trie 从而转化成树上的问题,题目是「arc087 E」

对于强制在线的待修改问题,可以考虑保存当前询问的前$k$个操作,回答每个询问时,先从一个不能修改的数据结构中取出一个基础答案,然后根据保存的操作进行修正。然后当保存的操作数大于$k$时,就对数据结构重建一下即可,题目是「BZOJ 3720」

数据结构题目,如果题目可以离线处理,首先想怎么离线做,离线做不了再考虑在线,「CF #453」没过 C 的原因。

使得 gcd 执行次数达到上界,只需要给两个相邻的斐波那契数即可,第$n$项和第$n - 1$项可以使其执行$n$次,题目「CF #453 div1 B」

有向图的生成树形图计数,对于边$u\rightarrow v$,可以使m[u][v]--,m[v][v]++,对于第$i$个点为根的外向生成树,去掉第$i$行第$i$列即可,题目来自「CodePlus 12 div1 t3」,然后求行列式就行了。

区间和的异或和问题,可以从两个前缀和的差值考虑,如果两个前缀和的差值在$mod\ 2^{k + 1} \geq 2^k$那么这段和的第$k$位就是$1$,题目来自「BZOJ4017」

BEST 定理」 有向图的欧拉回路数 = 以某个点为根的外向树形图个数 $\times \prod (deg_u - 1)!$
当然首先要验证图是否存在欧拉回路,题目是「BZOJ 3659」

「GarsiaWachs」算法,可以用于解决取石子的问题的特定算法。首先对于当前的序列,找到最小的$k$满足$a[k - 1] \leq a[k + 1]$,然后把$a[k - 1],a[k]$合并,计入代价。然后在$k-1$之前,找到最大的$j$满足$a[j]>a[k - 1] + a[k]$,然后把新和成的石子插入到$j$后面即可,维护时用链表即可。可以证明这样对应了一种最优的方案。题目是「BZOJ 3229」。

BFS序&DFS 序问题,可以考虑把点用 BFS 序重新标号来让题目的思考更简单,题目是「BZOJ3244」

二分图费用流,基于权值大小的匹配问题,可以考虑转化成括号匹配的模型来优化费用流的复杂度,题目是「BZOJ 4977」

FFT 时,如果次数不够,在 IDFT 时会自动把多出来的项溢出到前面。

拉格朗日插值法」考虑一个$k​$次多项式,因为繁琐的计算过程我们无法直接得到他的所有系数。但是如果我们能够提前获得其$k + 1​$个不同项的取值,就可以利用拉格朗日插值法在$O(k^2)​$的时间内计算出任意一项的取值。

直接介绍重心拉格朗日插值法的步骤,令$\vartheta (x) = \prod (x - x_i),w_i = \frac{1}{\prod\limits_{i \not= j} x_i - x_j}$

然后得到 $g(x) = \vartheta (x)\sum \frac{w_i}{x - x_i} g(x_i)$

同时还有一个小技巧就是,对于度数为$k$的多项式,取若干个点值,差分$k + 1$次后各项都是0。

题目参考「BZOJ 3453」

拉格朗日四平方和定理」简单的讲就是任意一个正整数都能拆分成四个完全平方数的和。我们考虑更一般的形式,即每个数最少可以用多少个完全平方数拼出来。

  • 对于答案为$1$的,我们开方验证一下即可。
  • 对于答案为$2$的,我们考虑把这个数质因数分解,对于所有满足$p \equiv 3 \pmod 4$的质因子,只要满足其指数为偶数即可(证明)。
  • 答案为$3$的,只要不满足其他情况。
  • 答案为$4$的,只要满足存在一对$a,b$可以满足$x = 4^a(8b + 7)$即可。

题目参考「BZOJ 2904」

「Kruskal 重构树」对于一个图来说,把所有边按边权递增排序,当合并两个联通块的时候,新建一个点。令两个并查集的根都指向这个新建的点,并且把这个点的点权赋为这个边的边权。这个树满足一个重要的性质就是他的子树中任意两个点都存在一条边权不超过根的点权的路径,题目参考「BZOJ 3551」

对于一个图的最小割来说,存在可行边和必选边两种,首先我们把跑完网络流后的残余网络跑一遍 scc 的算法,把每个 scc 缩点,考虑每条割边:

  • 如果是可行边,那么必定满足两个点属于不同的 scc。
  • 如果是必选边,那么必定满足scc[u] = scc[S],scc[v] = scc[T]

题目参考「BZOJ 1797」

2018 / 1

对于一类要求,构造一个字符串由一个串的子串拼接而成的题,可以考虑构造矩阵 $A$,$A_{i,j}$表示的是在母串中,长度最短的串满足首字母是$i$末子母是$j$且没在母串中出现过。然后就可以倍增的求出任意长度为的串的相关信息:比如长度,最少的串数,方案数等,题目参考「BZOJ 4180」。

平面图求任意两点的最短路,可以考虑平面图分治,每次选取较长边,取中间的一段,然后对中间的每个点求一遍单源最短路,更新所有询问即可,题目参考「BZOJ 4456」。

NIM 游戏中如果有取石数量的限制,对于每个石子堆对限制数量$+1$取模即可。阶梯博弈中,对于下标为偶数的石子堆可以直接无视。题目参照「BZOJ 3729」。

基于均摊复杂度分析的线段树,关键的一点是,通过维护极值与次极值的的大小来确定一个区间的信息是否需要重新计算。当我们对这个区间做修改之后极值和次极值的大小我们无法确定了,就需要重新计算区间的信息。题目参考「BZOJ 4355」。

伴随矩阵」简单的说,我们考虑矩阵$A$,对于其伴随矩阵$adj (A)$来说,$adj(A)_{i,j}$表示的是其$j$行第$i$列的代数余子式。同时我们知道,对于一个矩阵的行列式$det(A)$来说,可以按行或者按列展开为其一行或者一列的代数余子式的和。根据这一点,我们就可以在$O(n^3)$的预处理的情况下,当当前矩阵有某个值修改时,我们就可以用$O(1)$的时间求出其行列式的值。

至于如何求伴随矩阵,只需要把原矩阵求逆,然后对于每个元素乘上原矩阵的行列式,就是伴随矩阵。

题目参考「ZROJ 142」

对于一个看起来不好入手的题,先考虑费用流,如果可以方便的构造出费用流的解法但是数据范围过大,可以考虑费用流的本质,观察添加的反向边是否存在规律,是否可以通过数据结构来优化。题目参考「BZOJ 3252」。

「NIM-K 问题」即可以取不超过$D$堆石子堆的石子,对于这类问题的必胜状态,只要满足对于二进制的每一位,这一位为$1$的石子堆的数量刚好是$D + 1$的倍数的话,先手必败,题目参考「BZOJ 4550」。

「混合图欧拉回路」首先对于所有无向边,考虑把每条边随机定向,这样就把混合图变成了有向图,当然现在得到的无向图大概率是不满足存在欧拉回路的条件的,我们考虑调整一些边的方向。首先我们考虑所有点的入度和出度的差值,当我们调整一条边的方向是,一定是一个点的差值增加$2$一个点的差值减少$2$,接着我们考虑把所有差值为正的点连向源,负的连向汇,然后对于可调整边的点之间连边,跑一遍最大流,判断是否满流即可。

「随机增量法」常见于求最小圆覆盖,即在平面上用最小面积的圆覆盖所有的点。考虑动态的维护一个圆,每次考虑随机加入一个点,如果目前这个点在圆内,即不进行任何操作。否则我们可以知道首先当前这个点一定在圆的边界上,对于之前已经在最小圆覆盖中的点,我们考虑先暴力枚举另一个在边界上的点,之后检查是否可以完成覆盖,否则的话考虑另一个不在圆上的点一定在边界上,所以我们用这三个点确定新的圆,可以证明这样执行复杂度是$O(n)$的,题目参考「BZOJ 1337」

「树上依赖背包」可以考虑一种比较方便的方法,首先我们搞出树的 DFS 序,对于第$i$个点,设f[i][j]表示第$i$个地方代价为$j$的答案。首先考虑不选这个点的情况,如果不选这个点,那么对于这个点中的子树的点显然都不能选,所以我们直接继承f[i + siz[pos[i]]][j]的答案。接着考虑选这个点的情况,因为对于子孙关系的点对来说他们在 DFS 序上一定是包含的关系,所以我们直接拿f[i + 1][k]更新即可,题目参考「BZOJ 4182」。同时对于统计树上某个联通块信息的题,可以考虑点分治来处理。

「平面最近点对」一类要求平面上选择若干个点满足若干个点形成的多边形的距离最短。考虑分治做法,首先把所有点按照$x$的取值排序,对于当前我们处理到的$(l,r)$,我们取中间点$m$,我们先递归处理$(l,m)$以及$(m + 1, r)$,我们维护一个全局答案$ans$,然后取所有和$m$距离不超过$\frac{ans}{2}$的点。然后把这些点按照$y$的取值排序,双指针维护可能取到最优值的区间。然后在这个区间内暴力计算,更新答案即可,题目参考「BZOJ 2458」

「二进制分组」用于解决一类强制在线的问题,对于当前初始的数据结构,对其不断的进行修改和询问的操作。当我们被要求执行一个新的操作时,先把当前的操作保存下来扔到一个栈里,如果当前栈顶的修改数量等于栈顶下方那个集合的修改数量,就暴力将其合并。对于每个询问,直接对于栈里的每个集合分别进行询问即可,题目参考「BZOJ 4140」

对于一类询问出现次数相关的题,要考虑到两个比较关键的性质。

  • 不同的出现次数不会超过 $\log n$
  • 所有可能的二元组至多有 $n$个

题目参考「ZROJ 151」

点分树上如果满足一个点是另一个点的祖先,那么一定满足的是这个点是这两个路径上第一个选择的点,题目参考「BZOJ 3451」

如何快速的求一个点带权的重心,同时要支持修改点权的操作。我们考虑如果对于一条树边$x\rightarrow y$来说,如果满足$sum_y \geq all$那么重心一定在$y$的子树内。同时我们发现满足条件点序列一定是树上的一条链,而这个链的最底端就是我们要找的根,树剖后用线段树快速维护,题目参考「BZOJ 3924」

对于$O(k^3\log n)$线性递推,可以把利用特征多项式转化成$O(k^2\log k)$,资料看这里,题目可以看「BZOJ 4161」

一般图匹配,可以考虑随机匹配或者用一种基于线性代数的匹配方法。需要注意的是不管是随机匹配还是线性代数的方法都是随机的。随机匹配就是强制把原图看作二分图进行匹配,线性代数的方法直接看「2017 国家集训队论文」,说的很明白。

字符串的匹配问题要是遇到难以后缀数据结构解决的题,可以考虑 bitset 来维护,题目参考「CF 914F」

线段树区间除法:当区间内最大值和最小值整除下取整的差值相等时,整个区间打上减去这个差值的标记即可,题目「LOJ 6029」

对于线段覆盖的问题,要考虑到一个重要的贪心性质是按照所有线段按照左端点排序。对于每个线段来说,其最优的决策只有两个,一个是左端点之前的线段,一个是另一个线段的右端点在其右,并且左端点最靠左的线段,题目看这里

对于若干直线交于一个点的问题,可以把直线变化成点来考虑问题,题目参考「ZROJ 153」。

「sqrt decomposition」对于一类要求满足选择若干个元素满足某些位运算性质的,可以采用这个算法。例如求0/1十六维偏序的问题。朴素 DP 可以在$O(n^2)$的时间内处理,考虑用这个算法进行优化,我们设$f[pre][suf]$,即前半部分状态为$pre$,后半部分状态为$suf$的子集的所有状态的 DP 值的最大值。然后如果要更新当前点的状态$s$,我们枚举当前状态前半部分的子集更新即可,题目参考「CSA #67 E」。

2018 / 2

斯特林公式:$n! \approx \sqrt {2\pi n} (\frac{n}{e})^n$

Hall 定理:一个二分图存在完美匹配,当且仅当对于任意一个大小为 $k$ 的子集,其连向的另一个点集里的点数大于等于 $k$,当应用至 OI 里时,常用到的是一个推广出来的结论:当任意一个点连向的点是一个区间,而且任意两个点连向的区间不互相包含,那么我们只需要对任意区间检查 Hall 即可,题目 「BZOJ 2138」「BZOJ 1135」。

数论题目考虑打表看看是否存在积性,「ZROJ 157」

和树的重心相关的题考虑每个点到树的重心的路径是否存在某些性质,「LOJ 6042」。

棋盘覆盖问题要考虑二分图相关的理论,「UCS #4 G」

树的计数问题要考虑构造基尔霍夫矩阵手动消元观察是否存在规律,「LOJ 6044」

环上问题先考虑怎么在链上解决,「LOJ 6046」

平面上求画个多边形要求对某些整数点满足条件的题,可以考虑把平面拆成一维后用 FFT 加速判断,「LOJ 6049」

骨牌覆盖问题要考虑二分图染色,「HackerRank 101hack53 C」

2018 / 3

一个游戏的 SG 函数等于其所有子游戏 SG 函数的异或和,「arc091 F」。

二分图博弈问题,即给定一张二分图,初始有一个石子,两个玩家可以每次沿一条边移动石子,一个点只能经过一次,询问从某个点开始是否存在必胜策略。

首先给出结论,即对于一张二分图的所有最大匹配而言,如果一个点在所有最大匹配中,我们称之为关键点,那么从这个点出发就有必胜策略,下面考虑证明这个结论:

首先我们考虑,如果当前点是不是关键点的话,如果没有合法的连边,那么就失败了,如果存在合法的连边,其所有合法的连边都存在一个匹配,那么后手就沿着这个匹配走,这时候因为走出长度为偶数的交错路,我们把这条路径取反,可以证明当前的点也是非关键点。

如果当前点是关键点的话,那么沿着匹配边走,然后把这个点给删掉,这个时候我们走到的点就成了非关键点,沿用之前的证明。

然后我们考虑怎么快速的判定一个点是否是关键点,我们考虑网络流,即一定存在流量流过这个点。根据网络流关建边和可行边的那一套理论,我们发现在二分图建图的基础上跑网络流的话,对于连向源汇的边。如果这个边是可行边,那么这个边对应的边就是关键点。我们容易陷入一个误区就是认为关建边对应的才是关键点,因为对于一个匹配来说即 $S \rightarrow u \rightarrow v \rightarrow T$来说,三条边的流量都是 $1$,都可以成为割边,但是为什么可行边不会多算呢,目前还没有想清楚,但是花一些简单的图可以明显的说明这个情况。

最后因为其实二分图,所以我们并不需要再跑一遍 Tarjan,每次只要从 $S, T$ BFS 一遍即可。

「BZOJ 1443」「BZOJ 2437」

Borůvka’s algorithm 是一种快速找到一个图最小生成树的算法,也是这个第一个快速找到最小生成树的算法。大体上就是维护每个联通分量,最开始每个点单独作为一个联通分量。然后每次迭代时,考虑找到每个点最短的指向不同联通分量的出边,将他们合并,时间复杂度为 $O(n\log n)$,只需要迭代 $\log n$次就可以出解,「CSA #72 G」。

在 DFS 中,为了节省栈空间,可以使用 & 来引用变量的地址来节省内存的申请。

一个经典套路,之前竟然没发现,$f_n = f_{n - 1} + f_{n - 2}$ $(f_i,f_j) = f_{(i,j)}$

求一张图的最小割同时满足割边最少:构造一个新图满足新图的边的边权是原图的边数 + 1 倍再加 1,对新图跑一遍最小割,这个时候我们得到的流量对边数 + 1 下取整得到的是原图的最小割,余数即最小的边数。

一张联通图的生成子图数量是奇数当且仅当其没有奇环,否则即为偶数。

2018 / 5

计算三元环的一个比较套路的思考方向是根据度数分类讨论,对于度数 $\leq \sqrt m$ 的,暴力枚举每个点的任意两个边,对于度数 $\geq \sqrt m$ 的,点数很少,暴力枚举三个点即可,题目「BZOJ 5206」。

欧拉反演:$n = \sum\limits _{d | n} \phi (d)$ ,「BZOJ 3518」

对一个树,划分成 $k$ 个大小均匀的块的方案如果存在,那么是唯一的。同时,其如果存在,当且仅当存在不少于 $\frac{n}{k}$个点满足其子树的大小是 $k$ 的倍数,题目是「BZOJ 4401」。

对于询问第 $k$ 大类型的题目,如果总的复杂度是和$\sum k$ 相关的,那么可以考虑用堆来维护,即从现有的最优方案是否可以扩展出来次优的,「BZOJ 4504」「BZOJ 2006」

对于 DP 类型,满足决策单调性的题目,一般两种处理方法。一种是分治,另一种是二分 + 单调队列维护处理。

分治做法就是类似于整体二分的处理方法,不再多说。而单调队列的维护方式就是,我们对于队列里维护的每个决策,计算出来其比相邻的决策更优的时间,即进行到什么时候的时候另一个决策就没有用了。可以发现,我们维护的时间满足单调性即可,比如决策 $a, b,c$满足 $b$ 优于 $a$ 的时间晚于 $c$ 优于 $b$ 的时间,那么显然决策 $b$ 是无用的,「BZOJ 5311」。

泰勒展开 把一个连续函数拆分成一个,无限级数的形式。在 OI 里的作用是可以利用其的结合性,题目参考「BZOJ 5020」。

2018 / 6

一些最优化问题的思路:估测一个比较紧的下界,然后考虑是否可以构造出来一种方案可以达到这个下界,「THUSC2018D2T1」。

对于一些有特殊限制的图求单源最短路,同时每条边的边权都为正时,要考虑 dijkstra 时距离不减,利用这个性质在特殊图上可以优化,「BZOJ 4699」。

斐波那契数列在 $\mathrm{mod}\ 10^n$ 下的循环节为 $6\times 10^n$,「BZOJ 4294」。

2018 / 7

最小循环费用流

定义:有向图,每条边有一个容量和费用,要求选择若干个循环流,使得其费用最小。

构图:新建源汇,对于负权边 $u \stackrel{(cap, cost)}\rightarrow v$ ,拆为 $s \stackrel{(cap, 0)}\rightarrow v,v \stackrel{(cap, -cost)}\rightarrow u,u\stackrel{(cap, 0)}\rightarrow t$ ,其他保持一致。

然后从 $s$ 向 $t$ 跑最小费用最大流,拿答案加上所有负权边的权值与容量乘积即可,正确性显然。

集训考试的题目,大概就是类似于要求维护一个序列,使其支持左右两端插入,以及对某些信息作出询问。

题目中具体就是维护一个模意义下的背包,支持左右两端插入删除,以及询问模意义下容量在某一范围内的最大值。首先如果不要求强制在线的话就是个傻逼题,无脑线段树分治就做完了。然后我们考虑强制在线怎么做,首先简化一下,就是如果是左端插入,右端删除的话,考虑到背包插入是 $\mathcal{O(mod)}$ 的,我们维护两个分别向左右开口的栈,插入和删除可以直接维护,唯一的问题就是如果右边的栈删空了怎么办。我们考虑当右边的栈空了的时候直接将左边的栈开口方向转向,暴力重构一遍即可,算一下这样做的复杂度可以发现每个数最多只会参与一次重构,所以这个简化的版本就可以做到 $\mathcal {O(M mod)}$ 维护插入删除(先不考虑询问)。

然后考虑双端插入删除时怎么办,类似的,我们考虑当一段删完时怎么处理。我们考虑每次只将其中后一半转向重构,这样做复杂度仅多一个 $\log$,然后就做完了。

一个分块的小技巧,有时候一些数据结构题我们用莫队做的时候,需要维护插入,删除和找前驱后继,一般情况下用 set 之类的维护会导致多一个 $\log$ 。但是我们发现链表找前驱后继以及删除是 $\mathcal{O(1)}$的,但是无法支持快速的插入,所以我们可以分块建出一个大一点的,然后每次从两端向中间删除即可,雅礼集训看到的小技巧。

也是雅礼集训看到的小技巧,对于一个 $n \times m$ 的矩形来说,令 $f(x, y)$ 表示其中 $x\times y$ 的子矩形的数量。那么一定有 $f(n,m) = f(1, 1) - f(1, 2) - f(2,1) + f(2,2)$。

可以利用这个性质来解决一些计数的问题。

一个非负权边形成的树,令 $S$ 为树上一个点集,$f(S)$ 为这些点集所形成的直径,那么对于点集 $X,Y$ 来说 $f(X \cup Y)$ = $\mathrm{max\ dis(X_0,X_1),dis(X_0, Y_0),dis(X_1,Y_0), dis(X_1, Y_1)}$