Exqule Forever

Nothing with me, but Forever.

数据结构专练

发布于 2020-09-01 | 分类于 数据结构 、 二分答案 、 差分 、 树状数组 、 排序 、 线段树 | 14分钟 | 3466字数 | 浏览量：

数据结构专练

耗时一个暑假的成果，还算是稍有成绩。

线段树 SegmentTree\text{SegmentTree}

一些模板和较为基础的题目及记录：
稍加思考或较为套路的题目及记录：

考虑到单点查询可以转化为差分数组的前缀区间求和，差分数组便于处理修改操作。

考虑到将求区间方差公式拆开，则仅需要维护区间和以及区间平方和，区间平方和的维护也仅依赖于区间和。

考虑到一个非 11 的数开平方下去整的最多进行 log⁡n\log n 次，则将全部的数降至 11 仅需要 nlog⁡nn\log n 次。

那么对于一个全 11 的区间则不加以操作（操作后也不会发生任何改变），否则暴力递归进行开平方。

考虑到每次修改的颜色必然不同于之前出现的任何一种，那么统计已修改使用的颜色数。

当执行查询操作时，统计至此已使用了 kk 种颜色，而对于查询区间 [l,r][l,r] 没有出现的颜色数为 ww，那么答案即为 k−wk-w。此时需要求出 ww 的值，那么考虑没有出现第 ii 种颜色的充要条件是修改第 ii 种颜色时的修改区间 [li,ri][l_i,r_i] 与此时查询区间 [l,r][l,r] 没有交集。那么我们仅需要统计区间 [1,l)[1,l) 中出现的修改操作区间的右端点 rir_i 数，以及区间 (r,n](r,n] 中出现的修改区间的左端点 lil_i 数，那么 ww 即为两数之和。

大码农题 5.45KB\text{5.45KB}，建议口胡，可怜我还是写了一天。

考虑到区间覆盖 00 或 11 和区间翻转操作，统计求和十分容易处理，关键在与如何处理最长全 11 子串长度。而考虑到对于两个区间向上合并，最长全 11 子串为两个区间内最长全 11 子串长度，以及左区间中包含右端点的最长全 11 子串长度加上右区间中包含左端点的全 11 子串长度之和的最大值。

那么，由此考虑对于每个节点维护六个值 lw,rw,mw,Lw,Rw,Mw\text{lw,rw,mw,Lw,Rw,Mw}，分别表示区间内包含左端点的最长全 11 子串长度，包含右端点的最长全 11 子串长度，全区间内最长全 11 子串长度，区间内包含左端点的最长全 00 子串长度，包含右端点的最长全 00 子串长度，全区间内最长全 00 子串长度。

那么，对于区间覆盖操作 00 或 11，我们可以直接对 lw,rw,mw,Lw,Rw,Mw\text{lw,rw,mw,Lw,Rw,Mw} 进行赋值；而对于区间翻转操作，我们则考虑将 lw,rw,mw,Lw,Rw,Mw\text{lw,rw,mw,Lw,Rw,Mw} 进行 00 和 11 交换。

最后注意 lazy\text{lazy} 的标记处理。当进行区间覆盖 00 或 11 时，直接对于 lazy\text{lazy} 赋值；而进行区间翻转时考虑 lazy=0\text{lazy}=0 时则改为 lazy=1\text{lazy}=1；lazy=1\text{lazy}=1 时则改为 lazy=0\text{lazy}=0；否则直接记为翻转标记 lazy=2\text{lazy}=2。

考虑最终我们只关心位置 qq 上的值，那么考虑对于此处二分答案。

然后将原序列中大于假设值的赋值为 2，相等的赋值为 1，小于假设值的赋值为 0。此时我们利用线段树来模拟排序过程，那么此时我们可以通过区间查询和区间覆盖两种操作在 O(log⁡n)\text{O}(\log{n}) 的复杂度内完成操作。最后对于 qq 点的值讨论，此时如果值为 11 即为答案；否则值为 00 意味着实际答案小于此时假设值，相应地，值为 22 意味着实际答案大于此时假设值。据此我们发现其具有单调性，而不断调整二分区间，得到答案，时间复杂度为 O(n⋅log⁡n2)\text{O}(n\cdot { \log{n} }^2)。

思路偏难或难以处理的题目及记录：

经典维护区间历史最值操作的模板题，建议人人必刷。

详解可以查看下神犇灵梦的博客：区间最值操作与区间历史最值详解-灵梦。

如果您一眼看上去觉得这很显然可能需要再好好思索，因为你写到一半时，会发现常规的做法无法应对长期的区间加操作。因为无法及时的更新历史最大值，我们需要考虑维护历史最大加，同理需要维护历史最大覆盖。其实发现这点后就可以开始码题了，但是处理信息又成为了一点难题。

注意下线段树的一些细节有助于避免调试的复杂：

  1. Pushdown\text{Pushdown} 函数是关键中的关键，其中的内容应该与所有的 Update\text{Update} 函数中的完全区间操作对应。
  2. 写代码时处理速度足够快，足够熟练，也一定请把每个字符打完整，有时候能过编译而难以发现。
  3. 及时初始化数据，思路要清晰，变量名具有辨识度。
经典 GSS\text{GSS} 系列：

线段树维护静态区间最大子段和。

考虑两个区间合并时需要维护 44 个信息：区间和，区间最大子段和，区间最大左子段和，区间最大右子段和。这些信息可以相互维护，询问时我们直接合并两个子区间。由于没有修改操作，只需要建立 Build\text{Build} 函数和 Query\text{Query} 函数。注意，不存在不包含任何元素的子段。

本题为带单点修改版线段树维护动态区间最大子段和。

考虑到在 GSS1\text{GSS1} 的基础上我们只需要增加 Update\text{Update} 函数操作，由于是单点修改，故而不需要延迟标记，只需要在回溯过程中不断的合并修改后的区间，故而不需要 Pushdown\text{Pushdown} 函数。代码量仅增加 340 B\text{340 B} 左右。

本题和 洛谷-P4145 上帝造题的七分钟2 / 花神游历各国 题意一致，做法相同，此处省略，详情见上。

本题仍是基于 GSS1\text{GSS1} 上存在左右端点限制的线段树维护静态区间最大子段和。

分类讨论考虑两种情况存在不同答案，即端点所在区间是否重合。令此时询问为 [l,r][\text{l},\text{r}] 和 [L,R][\text{L},\text{R}]，当不存在重合时意味着，询问被划分成三个部分 [l,r-1],[r,L],[L+1,R][\text{l},\text{r-1}],[\text{r},\text{L}],[\text{L+1},\text{R}]，中间部分 [r,L][\text{r},\text{L}] 必然被选择，那么考虑对于左右部分的区间最大右子段和和区间最大左子段和。那么再利用已有信息就可以合并答案。

其次，当存在重合时意味着，询问也可以被划分成三个部分 [l,L-1],[L,r],[r+1,R][\text{l},\text{L-1}],[\text{L},\text{r}],[\text{r+1},\text{R}]，考虑中间部分最大子段和，中间部分区间最大左子段和和左区间最大右子段和，中间部分最大右子段和和右区间最大左子段和，左区间最大右子段和和中间全部分和右区间最大左子段和。依次取最大值。

细节处理，注意我们对于非空子段中负数部分考虑舍弃。

树状数组 BIT\text{BIT}

一些模板和较为基础的题目及记录：
稍加思考或较为套路的题目及记录：

考虑我们按照权值将二元组 (p,w)(p,w) 从小到大排序，依次插入序列中，每次插入前统计当前所有点与插入点距离的绝对值之和。此处考虑维护两个树状数组，一个维护权值和，另一个维护个数。

考虑按照权值将二元组 (p,w)(p,w) 从大到小排序，依次插入序列中，每次插入前统计位于此点之后的顺序对个数，组成三元上升子序列，计入答案；同时考虑统计位于此点之后的点数，组成以插入点为前的顺序对。此处考虑维护两个树状数组，一个维护顺序对数，另一个维护点数。

同时考虑相同元素对答案的影响，注意细节处理。

考虑到交换两个相邻的数即为求逆序对个数，所以我们需要对原序列应有的排列顺序予以编号。考虑按照序列 {a}\{a\} 作为标准，按照标准序列中从前至后的顺序依次对序列 {b}\{b\} 进行修改，注意相同元素的编号按照位置依次排列。再对编号完成的序列求逆序对个数，答案即为所求。

考虑到将值域为 [1,k][1,k] 的数予以重新排序后，大于 kk 的数所含逆序对将不产生影响。我们考虑统计对于每个值作为逆序对左端点的逆序对数，如果操作时的 a[k]a[k] 比历史最大操作值大，那么更新历史最大操作值，并且输出从 [ak+1,maxn][a_{k+1},maxn] 作为值域中所有数作为逆序对左端点的逆序对数，否则输出上次输出答案。

注意到这道题题面描述有点问题，对于交换操作前的逆序对 i<ji<j 我们考虑 ai≥aja_i\geq a_j 即为逆序对，交换操作后的逆序对 i<ji<j 我们考虑 ai>aja_i>a_j 为逆序对。注意处理此处细节。

思路偏难或难以处理的题目及记录：

考虑对于第 ii 位的每个字符 B,C,S\text{B,C,S} 记录前缀和为 ai,bi,cia_i,b_i,c_i，那么对于一个合法子串的起末位置 l,rl,r 必然满足 ar−al−1≠br−bl−1a_r-a_{l-1}\ne b_r-b_{l-1} 且 ar−al−1≠cr−cl−1a_r-a_{l-1}\ne c_r-c_{l-1} 且 br−bl−1≠cr−cl−1b_r-b_{l-1}\ne c_r-c_{l-1}。移项后得到 al−1−bl−1≠ar−bra_{l-1}-b_{l-1}\ne a_{r}-b_{r} 且 al−1−cl−1≠ar−cra_{l-1}-c_{l-1}\ne a_{r}-c_{r} 且 bl−1−cl−1≠br−crb_{l-1}-c_{l-1}\ne b_{r}-c_{r}。令 xi=ai−bi,yi=ai−ci,zi=bi−cix_i=a_i-b_i,y_i=a_i-c_i,z_i=b_i-c_i，那么考虑将每一个位置的三维前缀和转换为一个三元组 (xi,yi,zi)(x_i,y_i,z_i)，那么我们只需要考虑存在两个位置 l,rl,r 使得 xl≠xr,yl≠yr,zl≠zrx_l\ne x_r,y_l\ne y_r,z_l\ne z_r 即为合法子串，此时贡献为 r−l+1r-l+1，求最大贡献。

此时问题转化为一个三元组各不相同的问题，那么我们考虑如何化简题目。考虑对应三元组的贡献即为他所处在的位置，那么我们对于以 xx 为关键字排序后以 yy 为值域依次插入。注意如何除去 zz 的影响，我们考虑维护一个最值和次值，且包证两者的 zz 互不相同。当此时插入三元组的 zz 不同于最值的 zz 时考虑次值，否则考虑最值。

注意几个细节处理：当 xx 相同时一起操作；以 yy 为值域数组非负；不同贡献计入方式对应不同最值次值维护；由于我们直接利用前缀和处理，那么请将三元组 (x0,y0,z0)(x_0,y_0,z_0) 一并加入操作。

# 数据结构 # 二分答案 # 差分 # 树状数组 # 排序 # 线段树
2020.09.02-2020.09.05 学习日志 上一篇
博弈论杂题 下一篇
0%