UOJ Logo OldDriverTree的博客

博客

标签
暂无

[Ynoi2015]Day2题解

2019-10-28 10:48:32 By OldDriverTree

T1:いまこの時の輝きを(Version1)

Idea:hhf Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5071

一个数的约数个数即其每个质因子出现次数加上一然后乘起来

考虑对值域进行一次根号分治,这里取阈值为 $v^{1/c}$ ,大于阈值的数最多有 $c-1$ 个

我们把区间中所有大于阈值的质因子对答案的贡献用莫队维护,小于阈值的质因子的贡献每次暴力枚举质因子,然后即查其在区间中出现次数即可

总时间复杂度$O( (n+m)v^{1/c}/logv + cn \sqrt m )$,空间复杂度$O( nv^{1/c}/logv + m )$

对这题的评价:3/11

T2:どうか、忘れないで(Version1)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5072

考虑单次询问怎么算

对于数 $x$ ,假设出现了 $y$ 次,区间长度是 $len$

则 $x$ 对答案的贡献是 $x(2^{len-y}(2^y-1))=x(2^{len}-2^{len-y})$

$2^{len-y}$ 是除了 $x$ 之外的数有这么多个不同的子序列,这些对 $x$ 的贡献没有影响

$2^y-1$ 是所有 $x$ 构成的子序列中有这么多种至少包含一个 $x$ ,有 $1$ 种不包含 $x$

由于模数不同,不能用莫队直接维护

注意到贡献分为两部分 $x2^{len}$ 与 $-x2^{len-y}$

其中第一部分非常好维护

第二部分的贡献,可以把出现次数相同的数一起维护贡献

注意到一个区间中只有 $O( \sqrt n )$ 种不同的出现次数,这是一个自然根号

所以我们可以用一个莫队均摊地维护区间可能的出现次数,从而维护区间中所有出现次数

然后为了 $O(1)$ 实现快速幂,我们可以每次$O( \sqrt n )$算出

$2^1,2^2…2^{\sqrt n} % p$

以及$2^{\sqrt n},2^{2\sqrt n}…2^{ \sqrt n \times \sqrt n} % p$

这样就可以 $O(1)$ 快速幂了

还有一种方法是将出现次数排序,从 $2^x$ 转移到 $2^y$ 的时候的复杂度是 $log(y-x)$ ,类似于finger search的感觉,可以证明这个的复杂度是正确的

总时间复杂度 $O( n \sqrt m + m \sqrt n )$,空间复杂度 $O( n + m )$

对这题的评价:4/11

T3:世界で一番幸せな女の子(Version2)

Idea:lxl Solution:ccz Std:lxl Data:lxl

https://www.luogu.org/problem/P5073

考虑用线段树维护区间的一个凸的分段函数,这个分段函数其实也就是个半平面交

定义

cur -> L()为cur节点内部的左端最大前缀和的一个分段函数

cur -> R()为cur节点内部的右端最大后缀和的一个分段函数

cur -> MID()为cur节点内部的最大子段和的一个分段函数

cur -> L(x)代表cur节点整体被加了$x$后其最大前缀和

cur -> R(x)代表cur节点整体被加了$x$后其最大后缀和

cur -> MID(x)代表cur节点整体被加了$x$后其最大子段和

我们显然有

cur -> L(x) = max( cur -> left -> L(x) , cur -> right -> L(x) + cur -> left -> sum );

cur -> R(x) = max( cur -> left -> R(x) + cur -> right -> sum , cur -> right -> R(x) );

cur -> MID(x) = max( cur -> left -> MID(x) , cur -> right -> MID(x) , cur -> left -> R(x) + cur -> right -> L(x) );

由于两个段数分别为 $a$ 和 $b$ 的分段函数取max和加起来得到的分段函数最多有 $a+b$ 段,而且仍然都是凸函数

所以我们可以递归建线段树,然后由儿子归并得到其的分段函数

这里总复杂度是$T(n)=2T(n/2)+O(n)=O( nlogn )$的

这个其实和不带修改的线段树查询区间最大子段和类似,不过我们维护的是关于这个点被加了多少的一个分段函数从而计算出当前的最大前缀,最大后缀,最大子段和

然后考虑按照全局加有负数,可以按照全局加的这个东西离线,这样就可以做到$O( nlogn + mlogn )$了

总时间复杂度 $O( (n+m)logn )$,空间复杂度 $O( nlogn )$

对这题的评价:6/11

[Ynoi2015]Day1题解

2019-10-28 09:58:08 By OldDriverTree

T1:ただいま帰りました(Version3)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5068

考虑对每个点维护$n$个bitset,$f[i][j]$表示距离这个点小于等于j的点数

可以通过BFS来处理出这些bitset,每次查询的时候把一些bitset or起来就可以了

总时间复杂度$O( nm + { n \sum a } / w )$,空间复杂度$O( n^3/w )$,可以通过压位BFS来改进BFS的时间

对这题的评价:1/11

T2:いずれその陽は落ちるとしても(Version?)

Idea:ccz Solution:ccz Std:ccz Data:ccz

https://www.luogu.org/problem/P5069

如果一个位置 $x$ 是极大值(即 $a[x-1] < a[x] \ge a[x+1]$ ),那么 $x-1$ 和 $x+1$ 不会有机会成为最大值,且 $x$ 会成为最大值 $a[x]$ 次,此时可以把 $a[x-1]$ 和 $a[x+1]$ 直接设为 $0$ 而不影响答案

将 $a[x-1]$ 和 $a[x+1]$ 设为 $0$ 后可能会出现新的极大值,最终整个序列所有非 $0$ 位置都为极大值,非 $0$位置的值之和即为所求答案

分析以上找极大值的过程可知,实际上是从每个初始极大值开始向两侧隔一个位置取一个位置,直到遇到极小值($a[x-1] \ge a[x] < a[x+1]$)或边界($x=1$ 或 $x=n$)为止,一个极小值当且仅当在和两侧极大值距离均为偶数时会成为极大值

于是可以用数据结构维护极大值、极小值以及它们之间的区间

可以用平衡树/线段树维护极大值和极小值位置构成的序列,支持插入删除查询前驱后继,用树状数组/线段树分别维护原序列奇偶位置的前缀和,支持单点修改

也可以直接用线段树维护原序列,分类讨论两个区间信息合并的每种情况。

总时间复杂度$O( n + qlogn )$,总空间复杂度$O( n )$

对这题的评价:3/11

T3:たとえ未来が見えなくても(Version3)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5070

设我们需要输出长 $1$ 到 $k$ 的所有极长值域连续段个数

考虑扫描线,扫右端点,维护所有左端点的答案

对每个数,显然我们只需要考虑其离右端点最近的一次出现位置,记 $x$ 最近的一次出现位置为 $pos_x$

可以发现我们扫到 $x$ 位置,其值为 $a_x$ 时,我们只需要更新其对值域在 $a_x-k$ 到 $a_x+k$ 这个范围内的数的影响

我们从 $a_x$ 这个位置开始朝两边拓展,设现在的区间是 $[l,r]$ ,则每次根据 $pos_{l-1}$ 和 $pos_{r+1}$ 中离右端点最近的一个,拓展到 $l-1$ 或者 $r+1$

不失一般性设拓展到了 $[l-1,r]$ ,相当于说如果我们左端点到当前右端点的区间包含了 $pos_{l-1}$ ,则其存在一个长为 $r-(l-1)+1$ 的非极长值域连续段

显然对于 $x$ 我们最多拓展 $k$ 次,形成了一个类似阶梯的结构,于是可以处理出每个长度的值域连续段所对应的左端点的范围

维护 $k$ 个树状数组,对每个进行一次区间加操作,总共进行 $O(k)$ 次区间加操作即可

总时间复杂度 $O( (n+m)klogn )$,空间复杂度$O( n + mk/w )$

对这题的评价:4/11

[Ynoi2014]Day2题解

2019-10-27 11:52:44 By OldDriverTree

T1:帰らぬ者と、待ち続けた者たち(Version?)

Idea:kcz Solution:kcz/lca Std:kcz/lca Data:kcz

https://www.luogu.org/problem/P5065

将原序列分成k块,每个块维护块内每个长度下or的最大值

修改时,块内暴力重新计算每个长度下or的最大值,就是枚举右端点,然后到他的or和不同的左端点只有log种,枚举就可以了 时间复杂度$O(n/k \times log(n))$

询问时,答案在块内的情况: check每个块,如果可以把答案减少$1$,就更新答案,然后重复操作,否则退出 时间复杂度$O(k+n/k)$

如果答案跨过块,则从左到右枚举块,同时维护块左边所有不同的后缀or和 具体就是从一个块到下一个块的时候,把所有不同的后缀or和都or上自己整个块的or和,然后再加入自己所有不同的后缀or和(提前维护好)。之后去一下重 时间复杂度$O(k \times log(n))$

现在考虑答案右端点在块内,左端点在块左边的情况,然后从左到右枚举块内所有不同前缀or和(提前维护好) 如果他跟 当前最大的在块前面的后缀or和 的or和大于等于$k$,就更新答案并删除当前最大的在块前面的后缀or和,然后重复操作 否则退出。 时间$O(k \times log(n))$

$k$取$\sqrt n$时,

总时间复杂度$O(m sqrt(n) log(n))$

用一个线段树维护每个节点每种前缀 or 和以及每种后缀 or 和,然后暴力算出这两者一一对应的最优 or 和

再用一组堆维护每种长度上述所有的 or 和,再用一棵线段树维护每种长度 or 和的最小代价。查询时二分即可。

时间复杂度$O( mlog^2nlog^2a )$,其中修改一次的复杂度为$O( log^2nlog^2a )$,查询一次的复杂度为$O( logn )$,但是感觉平衡只能去掉$polyloglog(n)$,难以去掉log

对这题的评价:3/11

T2:誰も彼もが、正義の名のもとに(Version5)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5066

考虑用平衡树维护序列,将一段连续的同色极长段缩为一个点

发现操作具有对称性,本质上只有

区间染色为0/1

区间每个数or/and上左/右

区间和

这三种操作

发现第二种操作其实就是让区间中0/1的同色极长段各自向左/右扩散一格的位置

我们修改的时候不修改这个给定的区间,而是让区间两端点根据操作种类和所在的同色极长段的颜色进行调整,具体来说就是检查一下是否包含这个同色极长段,然后调节我们这次修改的区间的位置

然后问题便转化为,每次区间中0/1的同色极长段各自变大1或者缩小1,这个可以通过在缩点平衡树结构上打标记来实现

因为有可能一个同色极长段在缩了之后变成0,所以我们需要维护一下区间内最小的同色极长段长度,如果是0则暴力将其删去,同时合并两边的段

可以发现每次修改只会增加$O(1)$个同色极长段,每次删除可以花$O( logn )$的代价减少一个同色极长段

总时间复杂度$O( (n+m)logn )$,空间复杂度$O( n )$

对这题的评价:4/11

T3:消えない過去、消えていく未来(Version?)

Idea:mcfx Solution:mcfx Std:mcfx Data:mcfx

https://www.luogu.org/problem/P5067

题解 为了描述简洁,以下均用 $K$ 指代括号层数。

由于长度和操作次数同阶,以下均用 $N$ 指代这两个量。

算法 1

考虑用一棵树存储整个串。

查询时类似线段树或平衡树的区间查询。

对于第一个部分分,这棵树需要有 + - * 和数字几种节点。

+ 和 - 节点由于运算优先级相同,可以一起处理。

为了满足运算优先级的要求,需要数字节点的深度 > * 节点的深度 > + - 节点的深度。

显然,这样一棵树是非常容易构建的,可以直接当成非旋转 Treap,在合并操作时判断一下优先级即可。

时间复杂度:$O(N log N)$。

空间复杂度:$O(N)$。

期望得分:10 分。

算法 2

加上括号后,需要一种新的节点表示括号。

这里我们定义一种新节点 () ,表示一对括号。每个 () 节点有三个儿子,左儿子、右儿子和中儿子,左儿子和右儿子的含义与其他节点相同,中儿子表示括号内的表达式。 () 节点和其他节点合并时,优先级与数字节点相同。 对于不成对的括号,可以在原串最左边添加若干 ( ,最右边添加若干 ) 配成对,添加的括号显然是 $O(N)$ 的。

现在问题是如何构建一棵满足条件的树。

对于一个括号合法的表达式,可以从左往右扫一遍,用栈维护当前每层括号内的表达式。

当一对括号闭合时,添加一个 () 节点,中儿子指向内部的根,再与上一层合并即可。

查询时需要特判区间只包含一边括号的情况。

时间复杂度:$O(N log N ⋅ K)$。

空间复杂度:$O(N)$。

期望得分:20 分。

算法 3

考虑没有括号,但是有修改操作的情况。

当修改后的运算优先级不变时,可以直接修改。

如果修改后的运算优先级发生改变,可以先把该节点和左右的表达式分裂,修改完再合并到一起,这个可以用非旋转 Treap 很容易的实现。

时间复杂度:$O(N log N)$。

空间复杂度:$O(N)$。

期望得分:30 分,与算法 2 结合可得 40 分。

算法 4

如果同时有括号和修改,可以沿用算法 2 中树的结构。

对于修改操作,如果被修改的不是括号,可以与算法 3 类似的处理。不过这里只需要和最内层括号内的表达式分裂、合并。

如果修改了括号,可以把每个操作分解为若干个下列操作:

1.加入一个括号;

2.删除一对括号;

3.加入或删除一个其他节点。

第三种操作可以直接在 Treap 上处理。

第二种操作只需要把左节点、中节点、右节点依次合并即可。

对于第一种操作,多了一个不成对的括号,可以视为在无穷远处加了一个方向相反的括号。

如图,左边表示操作前树的形态,右边表示操作后的。圆点表示 () 节点,方点表示其他节点,圆点下方连接的节点表示括号内的内容。蓝色括号表示实际的括号位置,红色括号表示新加入的括号。

加入这两个括号后,需要新加入一个 () 节点,然后把每层括号的一侧分裂,然后合并到上一层。这个过程可以从上到下递归实现。

时间复杂度:$O(N log N ⋅ K)$。

空间复杂度:$O(N)$。

期望得分:100 分

可以利用splay来将时间复杂度改进到$O( N ( K + log N ) )$。

对这题的评价:5/11

[Ynoi2014]Day1题解

2019-10-19 02:35:57 By OldDriverTree

T1:太陽の傾いたこの世界で(Version1)

Idea:ccz Solution:ccz Std:ccz Data:ccz

https://www.luogu.org/problem/P5062

维护一棵红黑树(题意指的是对应2-3-4树的红黑树),可以发现每次插入后至多发生两次旋转。

旋转发生的情况是:一个黑点的孩子为一红一黑,但红色孩子有一个孩子为红色,此时视情况单旋或双旋。

不旋转而只调整颜色的情况是:一个黑点的左右孩子都是红色,且左右孩子中有一个有红色的孩子,此时将黑点的孩子设为黑色,黑点设为红色,继续考虑是否有两个红点是父子。

如果一个点的左或右孩子为空,那么有一个区间内的数插入后会在这个空位上,同时每个数也对应了一个空位,于是可以从空位开始,自底向上利用红黑树的结构和性质计算旋转次数。

对每个黑点,记录有几个数插入到子树中可以使黑点变红;

对每个红点,分别记录左右孩子变红的方案数(考虑左右孩子为黑点和为空的情况);

对每个点,记录子树中插入一个数,在子树内造成的旋转次数;

维护了这些信息,可以在插入时在根维护全局的答案。

查询的是分别插入$[1,x]$内的整数造成的旋转次数,只要找出x对应的空位,将这个空位到根的路径的答案重新计算,不考虑大于x的数的贡献,就得到了答案。

总时间复杂度$O( mlogn )$,空间复杂度$O( n + m )$

对这题的评价:3/11

T2:空の上の森の中の(Version1)

Idea:zcy Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5063

可以证明这个线段树只有$O( logn )$种不同大小的节点

对于每种节点大小分层,维护一个数据结构,支持:

1.区间加

2.单点修改

3.区间rank

这个是一个经典问题,目前离线上界是$O( m \sqrt n )$,在线上界是$O( m \sqrt {nloglogn} )$,我们通过一些规约证明了这个问题不弱于一个$\sqrt n \times \sqrt n$的矩阵乘法,所以目前认为难以达到$O( n \times polylogn )$的复杂度

可以证明线段树的每层只有$O(1)$种不同大小的节点,那么我们的总时间复杂度是

$O( m \sqrt n + m \sqrt {n/2} + m \sqrt {n/4} + ... )$ = $O( m \sqrt n )$

空间复杂度可以通过一些trick做到$O( n + m )$

对这题的评价:3/11

T3:この戦いが終わったら(Version3)

Idea:lxl Solution:shadowice1984 Std:shadowice1984 Data:lxl

https://www.luogu.org/problem/P5064

考虑值域分块,查询kth的时候先在值域分块上面找到kth属于哪个块,然后枚举块内元素即可

枚举块内元素时,即查询一个值是否在一个时刻属于一个连通块,在这个题里面由于支持撤销,所以需要使用时间复杂度$O( logn )$的按秩合并并查集,这部分是平凡的

然后考虑如何找到kth属于哪个块,一个简单粗暴的思路是并查集上每个点维护一个长度为$O( \sqrt {nlogn} )$的数组,即值域分块的数组,然后合并两个点的时候暴力把两个数组相加,这样我们就可以求kth了

这样空间复杂度是$O( n \sqrt {nlogn} )$的,会MLE,考虑如何优化空间复杂度

如果我们使用按size合并的并查集的话,可以发现这个并查集的树高是$O( logn )$级别的

可以发现我们每个连通块如果开一个数组来维护值域分块结构很浪费,因为对于小的连通块这个分块结构是非常不满的,而大的连通块个数很少

所以如果我们把数组换成一个有序的链表,即用链表来维护这个值域分块,此时我们的空间复杂度将会骤降至$O( nlogn )$

具体点来讲我们在并查集上每个节点维护一个链表,即启发式合并这个值域分块的链表,这里链表中的节点上存一个二元组$(id,cnt)$表示这个集合中有cnt个属于编号为id的值域块的点,查kth的时候for一遍这个有序的链表就可以了

如此这般分析的话我们会发现一个节点的链表size为$\min(size(p),\sqrt n))$

简单分析一下空间复杂度就是$O( nlogn )$的,因为每一个点最坏情况下会在每个祖先处被存储一次

然后考虑一下完全可持久化带来的影响

先将所有操作的版本树建出来,然后我们可以通过在版本树上面DFS来实现题目中的所有操作

每次撤销一个合并操作的时候,可以通过将两个值域分块的链表相减来实现,这个的时间复杂度还是$O( \sqrt {nlogn} )$的

总时间复杂度$O( m \sqrt { nlogn } )$,空间复杂度$O( nlogn + m )$

考虑怎么去掉log,并查集的这个log可以对原树进行分块之后加一些trick来去掉,空间的这个log可以通过逐块处理来去掉

总时间复杂度$O( m \sqrt n )$,空间复杂度$O( n + m )$

对这题的评价:4/11

[Ynoi2018]Day2题解

2019-09-16 12:24:16 By OldDriverTree

我信概最后写了个什么"从序列维护到动态图的数据结构概述"然后只拿了3.0,果然是傻逼课,建议大家转专业的话别选这个课。

T1:そらのおとしもの(Version2)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5397

http://www.51nod.com/Challenge/Problem.html#problemId=2046

"弑尽破净的第四分块" (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))

这题就是我想改一个已有的经典根号形式改出来,然后想了想发现可以做

考虑根号分治

定义一个值x出现次数为size[x]

如果没有修改操作,则预处理所有size大于$ \sqrt n$的值到所有其他值的答案,以及每个值出现位置的一个排序后的数组

查询的时候如果x和y中有一个是size大于$ \sqrt n$的,则可以直接查询预处理的信息,否则进行归并

$O( n \sqrt n + m \sqrt n )$

有修改操作即在这个做法上改良,因为发现这个做法的根号平衡并没有卡满,所以有改良余地

假设把所有x变成y

由于可以用一些技巧使得x变成y等价于y变成x,所以不妨设size[x] < size[y]

定义size大于$ \sqrt n$为大,size小于等于$ \sqrt n$为小

定义ans[x][y]为x到y去除附属集合的部分的答案(附属集合是什么下面有说)

x取遍所有值,y只有所有大的值,总$O( \sqrt n )$个

修改:

如果x和y均为大,则可以暴力重构,$O( n )$处理出y这个值对每个其他值的答案,因为这样的重构最多进行$O( \sqrt n )$次,所以这部分复杂度为$O( n \sqrt n )$

如果x和y均为小,则可以直接归并两个值的位置的排序后的数组,单次$O( \sqrt n )$,所以这部分复杂度为$O( m \sqrt n )$

如果x为小,y为大,发现小合并进大的均摊位置数为$O( n )$,对这个再次进行根号平衡

对于每个大,维护一个附属的位置集合,这个位置集合的大小不超过$O( \sqrt n )$

每次把小的x合并入大的y的时候,即合并入这个附属集合,并且用x到所有大的值的答案更新y到所有大的值的答案,这样

如果合并后附属集合大小超过$O( \sqrt n )$,则$O( n )$重构y到所有值的答案,这个过程最多进行$O( \sqrt n )$次,均摊复杂度$O( n \sqrt n )$

由于大的值个数$ \le \sqrt n$ , 附属集合大小$ \le \sqrt n$,这一部分是单次$O( \sqrt n )$的,所以这部分复杂度为$O( m \sqrt n )$

查询:

如果x和y均为大,则在维护的答案中查询min( ans[x][y] , ans[y][x] ),然后将x的附属集合和y的附属集合进行归并,这一部分是单次$O( \sqrt n )$的,所以这部分复杂度为$O( m \sqrt n )$

如果x和y均为小,则进行一次归并即可,所以这部分复杂度为$O( m \sqrt n )$

如果x为小,y为大,则在维护的答案中查询ans[x][y],然后将x和y的附属集合进行归并,这一部分是单次$O( \sqrt n )$的,所以这部分复杂度为$O( m \sqrt n )$

由于维护了所有可能的贡献,而且更新是取min,正确性也得到了保障

时间复杂度$O( (n+m) \sqrt n )$,空间复杂度$O( n \sqrt n )$

存在序列分块做法

对这题的评价:6/11

T2:ゴシック(Version2)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5398

https://cometoj.com/problem/1072

"点缀光辉的第十四分块" (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))

这题是我研究区间逆序对之后,枚举了一些区间pair贡献的题里面的一个

最开始枚举出来的时候我只会$O( n^{1.5+\epsilon } )$的暴力做法(实际上在n=1e5的范围内接近于$O( n^{7/4} )$),然后过了一年再看到这题就会了......

我们考虑莫队维护,不失一般性这里只讨论莫队的四种拓展方向里面的一种

每次把区间$[l,r]$拓展到$[l,r+1]$的时候需要维护$a[r+1]$和$[l,r]$这段区间的贡献

这里利⽤莫队二次离线的trick:

莫队就可以抽象为&n \sqrtm&次转移,每次查询一个序列中的位置对一个区间的贡献

这个贡献是可以差分的, 也就是说把每次转移的$a[r+1]$对区间$[l,r]$的贡献差分为$a[r+1]$对前缀$[1,r]$的贡献减去对前缀$[1,l-1]$的贡献

然后通过这个差分我们可以发现,我们把$O( n \sqrt m )$次的修改降低到了$O( n )$次修改,因为前缀只会拓展$O( n )$次

于是我们每次可以较高复杂度拓展前缀和,因为插入次数变成了$O( n )$次

然后这⾥我们离线莫队的转移的时候可以做到线性空间,因为每次莫队是从一个区间转移到另一个区间:

我们记下$pre[i]$为$i$的前缀区间的答案,$suf[i]$为$i$的后缀区间的答案

不失一般性,只考虑把区间$[l1,r1]$拓展到区间$[l1,r2]$:

$[l1,r1]$区间的答案为红色部分的贡献,$[l1,r2]$区间的答案为红色部分加上绿色部分的贡献,$r2$的前缀贡献为所有的贡献,$r1$的前缀贡献为红色的贡献与前两个蓝色的贡献

于是我们可以把绿色的贡献,也就是两次询问的差量差分为$pre[r2]-pre[r1]-${$[1,l1-1]$对$[r1+1,r2]$的贡献}

然后我们再差分⼀下$[1,l1-1]$对$[r1+1,r2]$的贡献为$[1,l1-1]$对$[1,r2]$的贡献减去$[1,l1-1]$对$[1,r1]$的贡献,这里每个位置开个vector存⼀下就可以了

于是我们达成了$O( n + m )$的空间复杂度将莫队给⼆次离线

现在考虑怎么算这个贡献,我们要高效计算区间$[l,r]$对$x$的贡献时

先把贡献拆开变成:$[l,r]$中$x$的倍数个数,$[l,r]$中$x$的约数个数

$[l,r]$中$x$的倍数个数:每次前缀加入一个数$a_i$的时候,我们把$a_i$的约数位置所对应的数组$pre1$的位置都++

然后查询的时候直接查$pre1[x]$即可得到$x$倍数个数

$[l,r]$中$x$的约数个数:这里考虑对$x$的约数进行一次根号分治

对于所有$x$⼤于$\sqrt n$的约数,我们拓展前缀的时候维护,即每次把$a_i$的倍数位置所对应的数组$pre2$的位置都++

然后查询的时候直接查$pre2[x]$即可得到$x$大于$\sqrt n$的约数个数

对于所有$x$小于$\sqrt n$的约数,我们考虑每次直接枚举区间$[l,r]$中$1,2,...\sqrt n$的出现次数

这里可以先枚举$1,2,...\sqrt n$,然后预处理一个前缀和,$O( n + m )$算出对每个询问的贡献,从而节省空间

于是我们得到了⼀个总时间复杂度$O( n( \sqrt n + \sqrt m ) )$,空间$O( n + m )$的做法

对这题的评价:8/11

T3:駄作(Version1)

Idea:lxl Solution:ccz Std:ccz Data:ccz

https://www.luogu.org/problem/P5399

https://loj.ac/problem/6612

"????的第七分块" (不中二了)

这个是我在军训走路的时候想出来的东西,然后我不会做,但是ccz会做

最开始给的做法是在静态top tree上跑莫队二次离线什么的,后面发现存在直接分块而不利用分治的做法,所以这题变简单了很多

这里只给出树分块做法,并不给出树分治做法

对于树上的顶点 $a,b$,顶点集 $S,S1,S2$,定义 $d(a,b)$表示顶点 $a$ 到 $b$ 的距离,若 $a=b$ 则 $d(a,b)=0$,否则 $d(a,b)$是 $a,b$ 间简单路径的边数; 另外定义 $d(S,a) = d(a,S) = ∑ d(a,b)[b∈S]$ $d(S1,S2) = ∑ d(a,S2)[a∈S1]$ 。

树 $T$ 上的一个邻域 $NT(x,y)$定义为到顶点 $x$ 距离不超过 $y$ 条边的顶点集。$x$ 称为邻域的中心, $y$ 称为邻域的半径。

真实的树分块——Topology Cluster Partition(名字正确性存疑)

树分块将 n 个结点的树分成了一些块的并,满足下列性质:

1.每个块是树

2.每个块中有两个特殊的点,称为端点 1 和端点 2。

3.不同块的边集不相交

4.一个块中的顶点,除端点外,其余顶点不在其它块中出现

5.如果一个顶点在多个块中出现,那么它一定是某一个块的端点 2,同时是其余包含这个顶点的块的端点 1

6.如果把所有块的端点作为点,每块的端点 1 和端点 2 连有向边,则得到一棵有根树

这里给出树分块的一个实现,满足块数和每块大小均为 $O( \sqrt n )$:

在有根树中,每次选一个顶点 $x$,它的子树大小超过$\sqrt n$,但每个孩子的子树大小不超过$\sqrt n$, 把 $x$ 的孩子分成尽可能少的块(以 $x$ 为端点 1,但暂时允许有多个端点 $2$,且每块至多有 $2 \sqrt n$ 个顶点),然后删掉 $x$ 的子树中除 $x$ 外的部分。重复直到剩下的点数不超过$\sqrt n$,自成一块。 这样就求出一个保证块中顶点数和块数均为 $O( \sqrt n )$的树分块(块间可以共用一些顶点,但每条边只属于一个块),如果一个块有多个端点(即被多个块共用的点),则在块内将这些端点建出虚树,将虚树上的每条边细分为一个新的块,以保证最终每个块只有两个端点。

如果只有单次询问,可以进行转化: $d(S1,S2) = ∑[d(a,c)*|S2|+d(b,c)*|S1|−2d(lca(a,b),c)][a∈S1,b∈S2]$,其中 $c$ 是任意一个点。这里我们取$c$为根节点,这样把两两顶点间的距离和转化为了点集内顶点的深度和以及两两顶点间 lca 的深度和: $d(S1,S2) = ∑[dep(a)*|S2|+dep(b)*|S1|−2dep(lca(a,b))][a∈S1,b∈S2]$ 对 lca 部分可以在$ O(n)$时间内求出:初始化树的边权为 $0$,将 $S1$ 中的每个顶点到根的路径的边权$+1$,求 $S2$中每个顶点到根的路径的边权和之和。

首先进行树分块,方便起见,认为一个块包含块中除了端点 $1$ 之外的点,这样每个点就恰好属于一个块。 预处理每个块 $B$(端点为 $a1,a2$)中的 $d(NB(ai,x),aj)(i,j=1,2)$,需要 $O(n)$时间和空间。

树 $T$ 的一个邻域可以拆分为这个邻域和每个块的交。

对于块 $B$,若 $x$ 在 $B$ 中,则 $NT(x,y)∩B=NB(x,y)$; 否则设 $z$ 是 $B$ 中距离 $x$ 较近的端点,距离为 $d$,则 $NT(x,y)∩B=NB(z,y-d)$。

求两个邻域间的距离和,只需考虑这两个邻域和每个块的交。求块 $B1,B2$ 的两个邻域 $n1=NB1(x1,y1)$和 $n2=NB2(x2,y2)$间的距离和。 如果 $xi$ 不是 $Bi$ 的端点,则显式地求出 $ni$ 以及 $ni$ 到 $Bi$ 的端点的距离和,这需要 $O( \sqrt n )$的时间。

当 $B1≠B2$ 时,设 $a$ 为 $B1$ 中最靠近 $B2$ 的端点,$b$ 为 $B2$ 中最靠近 $B1$ 的端点,$n1$ 和 $n2$ 间的距离和 $d(n1,n2)=d(a,b)*|n1|*|n2|+d(n1,a)*|n2|+d(n2,b)*|n1|$。通过在块构成的树上 dfs,这部分可以在 $O( \sqrt n )$时间内处理。

当 $B1=B2$ 时,如果 $x1$ 和 $x2$ 都是 $B1$ 的端点,每块每次询问这种情况出现至多 $1$ 次,这里暂不考虑,最后再离线处理;否则每次询问这种情况只出现 $O(1)$次,可以 $O( \sqrt n )$暴力处理。

离线处理的部分,枚举每个块 $B$,再枚举询问(只需考虑两个邻域的中心都不在 $B$ 中的询问) 计算贡献,有 $O(n)$个询问形如 $d(NB(a,y1),NB(b,y2))$,对<$a,b$>的 $4$ 种情况分别计算。由于块中 点数的限制,<$y1,y2$>实际只有 $O(n)$种($y1,y2=O( \sqrt n )$)。 仍然转化为求两两点间 lca 的深度和,枚举 $y1$,维护初始边权为 $0$,将 $NB(a,y1)$中每个点到 根路径上的边权$+1$ 后得到的树,此时每个 $y2$ 对应的答案是 $NB(b,y2)$中每个点到根的路径的边权和之和。这部分时间和空间都是 $O(n)$的。

时间复杂度$O( (n + m)\sqrt n )$,空间复杂度$O( n+m )$

最后推荐一下这个gal,挺好玩的

对这题的评价:10/11

[Ynoi2018]Day1题解

2018-12-12 16:09:11 By OldDriverTree

我信概写了3000字才写了一半(老老实实写ML和AI多好啊)

T1:いろとりどりのセカイ(Version3)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problemnew/solution/P4117

https://www.lydsy.com/JudgeOnline/problem.php?id=5143

http://codeforces.com/problemset/problem/896/E

"突刺贯穿的第二分块" (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))

这题的来源比较神奇,大概是csy搬了一个全局大于x的减x,查kth什么的题,然后我想把这个出区间上

然后直接出会得到一个$O( n \sqrt n logn )$的废物,当时想了很久都没想到什么trick能做值域1e9的情况(有没有人教教我啊)

然后改了改发现值域1e5是可以做的就出了出来

考虑分块,可以发现每块的最大值总是不增的

总的所有块的最大值和当块大小为$O( \sqrt n )$时为$O( n \sqrt n )$

考虑怎么利用这个性质

可以发现:假设区间所有大于x的减x,最大值为v

这个操作等价于把区间中所有数减x,之后小于x的再加x

当$v > x \times 2$时,可以把所有$[1,x]$内的数合并到$[x+1,x \times 2]$上

当$v \le x \times 2$时,可以把所有$[x+1,v]$内的数合并到$[1,v-x]$上

如果$v > x \times 2$

我们用$O( x ) \times O( Data Structure )$ 的代价使得块内的最大值减少了$O( x )$

如果$v \le x \times 2$

我们用$O( v - x ) \times O( Data Structure )$ 的代价使得块内的最大值减少了$O( v - x )$

所以要用一个数据结构支持:

$O( 1 )$把块内值为x的全部变成$x+v$

$O( \sqrt n )$求出块内经过大量操作后,每个数的值

第一种是整块操作的时候要用

第二种是重构零散块的时候要用

维护这个有很多种方法

可以每块维护一个值域上的链表

1.定义f[i][j]为第i块里面所有值为j的数的下标的链表

区间所有x变成x+v即link( x , x + v )

然后维护一下块内可能出现的所有数

每次重构的时候即遍历所有可能出现的数,然后遍历其中真正出现的数的链表即可

不过链表常数巨大。。。

这个应该跑的很慢

2.可以每块每个值维护一个vector

然后启发式合并这个vector

这个做法由于对缓存友好,所以会跑的快一些

3.可以用一个并查集维护

这个并查集由于只支持:

  1. merge( x , y )

  2. for( i = 1 ; i <= sqrtn ; i++ ) find( i )

所以复杂度是$O( 1 )$的并查集

本质上和链表的做法是差不多的,不过常数好很多

如果认为值域和n同阶的话(本来也是这样设计的)

时间复杂度$O( (n + m) \sqrt n )$,空间复杂度$O( n \sqrt n )$,可以使用逐块处理的trick把空间复杂度降低到 $O( n + m )$。

顺便这题的Version4是查询区间rank,我记得当时我用当时感觉挺厉害的trick做到了和现在一样的复杂度不过感觉不practical所以没有挂出来

对这题的评价:6/11

T2:終末なにしてますか?忙しいですか?救ってもらっていいですか?(Version6)

Idea:lxl&zyz Solution:ccz Std:lxl Data:lxl

https://www.luogu.org/problemnew/show/P4680

https://www.lydsy.com/JudgeOnline/problem.php?id=5144

"深浅值藏的第六分块" (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))

这题好像是当时zyz在某群里面问全局加区间最大子段和怎么做,然后我当时也只会$O( n \sqrt n )$的暴力做法(菜的扣脚)

然后NOI的时候突然想起来然后去问ccz,然后ccz秒出了一个$O( nlog^2n )$的做法,然后我NOI就挂了所以我就没去管这题了

然后我在学文化课养老的时候突然发现有人在bzoj上挂了一个区间加区间最大子段和。。我当时的心情大概就是:\吐血

https://www.lydsy.com/JudgeOnline/problem.php?id=5089

然后发现和我是一样的做法,但是我觉得很不服(明明是我先出的题,怎么就(虽然没挂出来所以其实不能算先出吧))

去和ccz聊了聊,发现区间加区间最大子段和可以做到$O( n \sqrt nlogn)$,然后又想了想发现可以做到$O( n \sqrt n )$(ccz太强了)

先考虑全局加区间最大子段和怎么做

考虑用线段树维护区间的一个分段函数,这个分段函数其实也就是个半平面交

定义

cur -> L()为cur节点内部的左端最大前缀和的一个分段函数

cur -> R()为cur节点内部的右端最大后缀和的一个分段函数

cur -> MID()为cur节点内部的最大子段和的一个分段函数

cur -> L(x)代表cur节点整体被加了x后其最大前缀和

cur -> R(x)代表cur节点整体被加了x后其最大后缀和

cur -> MID(x)代表cur节点整体被加了x后其最大子段和

我们显然有

cur -> L(x) = max( cur -> left -> L(x) , cur -> right -> L(x) + cur -> left -> sum );

cur -> R(x) = max( cur -> left -> R(x) + cur -> right -> sum , cur -> right -> R(x) );

cur -> MID(x) = max( cur -> left -> MID(x) , cur -> right -> MID(x) , cur -> left -> R(x) + cur -> right -> L(x) );

由于两个段数分别为a和b的分段函数取max和加起来得到的分段函数最多有a+b段

所以我们可以递归建线段树,然后由儿子归并得到其的分段函数

这里总复杂度是$O( nlogn )$的(带一个大常数)

这个其实和不带修改的线段树查询区间最大子段和类似,不过我们维护的是关于这个点被加了多少的一个分段函数从而计算出当前的最大前缀,最大后缀,最大子段和

然后考虑怎么拓展到区间加

如果强上分块的话复杂度是$O( n \sqrt (nlogn) )$的(实测应该会被卡)

发现我们这个线段树其实只是一个分治结构而已,不涉及到大量在上面的查询操作

每次重构零散块的时候,可以发现每层只用重构操作边界上的$O( 1 )$个节点,而不用重构整个线段树

于是重构复杂度是$O( \sqrt n + \sqrt n / 2 + \sqrt n / 4 + ... ) = O( \sqrt n )$

于是做到了

时间复杂度$O( (n + m) \sqrt n )$,空间复杂度$O( nlogn )$

据说用什么闵可夫斯基和可以做到同样的复杂度但是好写一些常数也小一些?反正我不会

上述题解是针对Version5,也就是说区间加正数来做的,对于区间加任意数,我们考虑对每个块离线进行基数排序,注意逐块处理,这样就可以通过 $O( (n + m) \sqrt n )$ 次操作转化为区间加正数的问题了。

离线逐块处理可以让空间复杂度变成 $O( n )$。

时间复杂度$O( (n + m) \sqrt n )$,空间复杂度$O( n )$

P.S这题我写的极其恶心写了一周(虽然就是每天逃几节课来写的)

对这题的评价:7.5/11

T3:未来日記(Version2)

Idea:fdy Solution:fdy&lxl Std:lxl&csy Data:lxl

https://www.luogu.org/problemnew/show/P4119

https://www.lydsy.com/JudgeOnline/problem.php?id=5145

http://acm.hdu.edu.cn/showproblem.php?pid=6079

"望月悲叹的最初分块" (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))

这个是这个系列中第一个被出出来的题,当时给了多校(然后的确没人做出来耶),然后被搬到了毛营(然后还是没人做出来耶)

这个是我同学出的,不是我出的(当时问我我也不会这题来着),来源似乎是有个$cdqz$高新校区的小朋友看错了一个cf题,然后被加强造出来的

这里就直接挂csy的题解了,和我的不太一样,但是大概思路还是差不多的,我的做法是和T1有点类似的维护方法

先考虑如何求区间第$k$小值。对序列和权值都进行分块,设$b_{i,j}$表示前$j$块中权值在$i$块内的数字个数,$c_{i,j}$表示前$j$块中数字$i$的出现次数。那么对于一个询问$[l,r]$,首先将零碎部分的贡献加入到临时数组$tb$和$tc$中,然后枚举答案位于哪一块,确定位于哪一块之后再暴力枚举答案即可在$O( \sqrt n )$的时间内求出区间第$k$小值。

接着考虑如何实现区间$[l,r]$内$x$变成$y$的功能。显然对于零碎的两块,可以直接暴力重构整块。对于中间的每个整块,如果某一块不含$x$,那么无视这一块;否则如果这一块不含$y$,那么只需要将$x$映射成$y$;否则这一块既有$x$又有$y$,这意味着$x$与$y$之间发生了合并,不妨直接暴力重构整块。因为有$c$数组,我们可以在$O(1)$的时间内知道某一块是否有某个数。

考虑什么情况下会发生重构,也就是一个块内发生了一次合并的时候。一开始长度为$n$的序列会提供$O(n)$次合并的机会,而每次修改会对零碎的两块各提供一次机会,故总合并次数不超过$O(n + m)$,因此当发生合并时直接重构并不会影响复杂度。

那么现在每块中的转换情况只可能是一条条互不相交的链,只需要记录每个初值转换后是什么,以及每个现值对应哪个初值即可。遇到查询的时候,我们需要知道零碎部分每个位置的值,不妨直接重构那两块,然后遍历一遍原数组aa即可得到每个位置的值。

在修改的时候,还需要同步维护$b$和$c$数组,因为只涉及两个权值,因此暴力修改$j$这一维也是可以承受的。

总时间复杂度$O((n + m)\sqrt n )$,空间复杂度$O( n \sqrt n )$

对这题的评价:8.5/11

[Ynoi2016]Day2题解

2018-12-11 12:14:12 By OldDriverTree

我感觉我信概药丸了(为啥非要作死写奇怪的东西呢)

T1:JabberWocky

Idea:lxl Solution:lxl Std:lxl Data:lxl&zcy

https://www.luogu.org/problemnew/show/P4118

https://www.lydsy.com/JudgeOnline/problem.php?id=5394

首先要会拓展欧拉定理(我一个出数据结构的怎么就开始数论了呢)

$a^x\;mod\; p\;=\;a^{x\;mod\;Φ(p)+(x>Φ(p)?Φ(p):0)}\;mod\;p$

然后可以发现对一个数取欧拉函数,log次就会变成1(这个性质烂大街了吧),然后任何数mod 1都是0就可以停下来了(不要停下来啊)

然后直接这样写会发现WA了(这种东西肯定会有一堆细节啦)

以下这段抄自zcy的题解:

首先我们发现后面的phi[p]这一项是可能不会加的。这个怎么办呢?

首先可以按照相逢是问候那题的套路返回判断是否取模,以此作为是否加上这一项的依据。

当然这么做需要讨论的东西会有点多,挺麻烦的。

后来就想到了也写在讲评里的办法,就是因为这个不断地幂次增长速度极快,很少几项就能够增长到远大于模数的地步。

那就先暴力的处理前面几项,然后再正常做,这样就减少了讨论次数。

但是这么搞还会存在一个问题,就是如果前几个常数次暴力处理的全是1,增长就是假的。

不过考虑到有1的话后面的全都被变成了1,所以完全没有必要担心这个,找到1就从1开始做好了。

然后还会存在一个问题,就是如果得到的是0次方,$x^0 = 1$

这个虽然数据不会存在这个问题,但是取模后会出现。

这个地方稍微注意一下就好了。

然后应该就没有什么坑了。

时间复杂度应该是 $O( mlognlog^*v )$

空间复杂度 $O( n + m )$

对这题的评价:3/11

T2:Which Dreamed It

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problemnew/show/P4692

https://www.lydsy.com/JudgeOnline/problem.php?id=5395

思路非常简单,就每个颜色在每一段开一个set,然后每次修改的时候计算一下贡献就可以了

有一些细节需要注意

时间复杂度 $O( ( n + m )logn )$ , 空间复杂度 $O( n + m )$

对这题的评价:3/11

T3:JabberWockyII

Idea:ccz Solution:ccz Std:ccz Data:ccz

https://www.luogu.org/problemnew/show/P4693

https://www.lydsy.com/JudgeOnline/problem.php?id=5396

这是一道简单模拟题。

可以将有根有序树动态地剖分为一些水平路径和竖直路径,满足性质:

1.竖直路径表示一个点序列,每个点是上一个点的孩子;

2.水平路径表示一个点序列,这些点的父亲相同,每个点是上一个点右边的第一个点;

3.树上每个点在且只在一条路径中出现;

4.对每个点,它的孩子可以被表示成0到2条水平路径,除了至多一个点在某条竖直路径上。

不难实现两个操作:

水平访问:给定一个点w,保证w有至少一个孩子,将w的孩子表示为一条水平路径;

竖直访问:给定一个点w,将w在树上到根的路径变为一条两端为w和根的竖直路径。

接下来不难进行每个操作:

A和B是把一条路径从水平变为竖直或从竖直变为水平,可以打标记实现,注意维护4条性质

C为换根,竖直访问然后打上翻转等标记,需要注意对孩子顺序的规定

D和E只需进行水平/竖直访问然后进行普通的区间修改查询

F为初始化,略

可以发现竖直路径的变化和lct很接近,因此复杂度分析可以参考lct的一些结论。

时间复杂度 $O( mlog^2n )$ , 空间复杂度 $O( n + m )$

据@negiizhao 说可以做到 $O( mlogn )$?

对这题的评价:10/11

这套题就T3比较毒瘤,其他都很简单吧

按照惯例放上可爱的妹子的图:

[Ynoi2016]Day1题解

2018-12-10 13:51:39 By OldDriverTree

最近正好在写信概的小论文一样的东西所以顺便把这个写了吧

T1:Down The Rabbit Hole

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problemnew/show/P4688

https://www.lydsy.com/JudgeOnline/problem.php?id=4939

https://loj.ac/problem/6199

可以发现就是求每个数在多个(这里其实可以任意个的)区间里面的出现次数的min

首先想到可以高维莫队,但是复杂度相当地高(主要是常数也很大),所以是过不了的

先考虑如果这三个区间里面每个数最多出现一次的话怎么做,可以想到莫队跑区间搞出每个区间的值域上的bitset,然后and起来,然后count一下就是每个数在这些区间里面出现次数的min了

但是如果有重复的数似乎就没法bitset了?其实是可以的

考虑进行离散化的时候,有一种写法是a[i] = lower_bound( b + 1 , b + n + 1 , a[i] ) - b这样的,相当于给出现次数为x的数留下了x个位置

先离散化,假设数x离散化后的位置是y,然后x出现z次

那么y,y+1…y+z-1这些位置都是x的

莫队维护区间bitset的时候

假设区间中y出现了w次

则我们把y,y+1…y+w-1这些位置填上1

y+w…y+z-1这些位置填上0

比如1 1 1 3 3 3 5 5 5 5 7离散化之后:

然后跑莫队维护区间的bitset,这个时候把每个数放到其离散化后对应的位置开始第一个非空的位置,这样每个数就是连在一起的了,就像这样:

然后我们把每次查询对应的区间的这样的bitset and起来然后count一下就得到了每个数在这些区间中出现次数的min,然后差不多就得到答案了

注意到存下$3 \times 10^5$个长为$10^5$的bitset是一件对空间很毒瘤的事情,所以要分几组跑莫队,不过由于bitset是瓶颈所以这里对时间复杂度和实际运行时间没什么影响

时间复杂度$O( nm/w )$,空间复杂度$O( nm/w )$

对这题的评价:3/11

T2:It's My Own Invention

Idea:lxl改编 Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problemnew/show/P4689

https://www.lydsy.com/JudgeOnline/problem.php?id=4940

https://loj.ac/problem/6200

这题的题目名有一种嘲讽的意味(因为这题不是我自己的发明)

来源是一个cf题,然后好像当时被人搬到了SNOI,然后我看了看题感觉还行就改编了一下(其实就是套了个壳子什么的never mind)

发现这个是一个换根然后查子树的问题,这个是一个非常经典的套路——就是假的换根,答案可以被差分为原DFS序上的区间信息

然后查询[l1,r1],[l2,r2]可以按二维前缀和差分为

可以差分为:

F(l1,r1,l2,r2)=F(1,r1,1,r2)-F(1,l1-1,1,r2)-F(1,r1,1,l2-1)+F(1,l1-1,1,l2-1)

这样都变成了前缀的区间之间的贡献

然后就可以在这个上面跑莫队了

这个题m=5e5,然后这个差分会导致最多差分出9个询问

询问最后有5e6个左右,排序的O( mlogm )比较慢

可以考虑对莫队的询问进行基数排序

时间复杂度$O( n \sqrt m + m )$,空间复杂度$O( n + m )$

对这题的评价:3.5/11

T3:Looking Glass Insect

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problemnew/solution/P4690

https://www.lydsy.com/JudgeOnline/problem.php?id=4941

https://loj.ac/problem/6201

区间染色是有一个均摊性质的

每次区间染色,最多在左端点,右端点处产生两个新的颜色段

所以由于区间染色每次最多只会增加$O( 1 )$个连续颜色段,用平衡树维护所有连续段即可

均摊的颜色段插入删除次数$O( n + m )$

考虑维护每个点与其颜色相同的前驱

发现一个颜色连续段里面除了第一个点以外,后面的点i的前驱都是i-1

用树套树/分治维护,于是这个颜色段的变化可以$O( log^2n )$维护

时间复杂度$O( ( n + m ) log^2n )$,空间复杂度$O( n + m )$

这题不同写法导致的常数可能差5倍(我最开始的写法就是这样的),所以比较诡异,顺便这题细节挺多的(小声)

对这题的评价:4/11

这套题也就这样了(大概是我两年前出的题了吧所以难度很一般),如果大家有兴趣去看看也好吧(不过感觉已经有些过时了)

忘记放可爱的妹子的图片了:

三道经典分块题的更优复杂度解法&[Ynoi2019模拟赛]题解

2018-11-20 19:52:35 By OldDriverTree

大概是一年前搞的东西了,一直都懒得发博客

1.强制在线的区间逆序对

目前我能做到 $O( n\sqrt m )$ 空间, $O( n\sqrt m )$ 时间

大概有5,6种做法吧,这里讲一个常数最小的

预处理前缀块到前缀的答案,然后每次可以大力差分为一堆已经预处理的东西,以及两个块的零散互相的贡献

前者已经预处理了,直接查表就可以了,后者可以归并计算

可以在这里提交https://www.luogu.org/problemnew/show/P5046

2.允许离线的区间逆序对

目前我能做到 $O( n + m )$ 空间, $O( n\sqrt m )$ 时间

这个算法是基于“莫队算法”的,个人将其命名为“莫队二次离线”,如果大家觉得有问题请提出然后我改掉就是

原理大概是把莫队抽象为 $O( n\sqrt m )$ 次查询区间中小于x的数的个数

然后差分为 $O( n\sqrt m )$ 次查询前缀中小于x的数的个数

然后可以发现这里有很大的不平衡——查询次数 $O( n\sqrt m )$ ,但是区间长度只有 $n$ ,也就是说不同的前缀只有 $n$ 个

考虑用一个 $O( n\sqrt n )$ 插入, $O( 1 )$ 查询的rank的数据结构,即一个普通的值域分块来维护

这样就达到了我们需要的时间复杂度

如果存下每次询问,那由于莫队会造成 $O( n\sqrt m )$ 次前缀查询,所以空间复杂度还是很高的

考虑到莫队每次是一个区间到一个区间的转移,也就是说大部分查询是有规律的,这里是可以优化到 $O( n + m )$ 的空间的

目前这一步最优的实现方法是再大力差分一下,通过前缀对前缀的贡献,后缀到后缀的贡献,以及一个序列区间对一个前缀的贡献,后缀的贡献来表示每次莫队转移的时候造成的贡献,这个实现有着不错的常数以及代码复杂度

可以在这里提交https://www.luogu.org/problemnew/show/P5047

3.强制在线的区间众数查询

目前我能做到 $O( n )$ 空间, $O( n\sqrt m )$ 时间

这个算法并不是我独立提出的

考虑预处理块端点到块端点的众数,然后每次就需要查询 $O( n/\sqrt m )$ 个数加入一个块端点到块端点的部分可能对答案造成的影响

以前的OI界传统做法是搞一个值域分块,然后每次 $O( 1 )$ 查询一个数在一个区间中出现次数

但是我们的问题实际上比这个弱很多——我们只需要 $O( 1 )$ check if这个数在这个区间中出现次数为ans+1即可

对每个值开一个vector,按顺序维护这个值的所有下标

假设现在在check x,然后x在其的vector的y位置,然后我们只需要check if 这个vector的y-ans,y+ans位置在我们查询的区间 $[l,r]$ 内即可

由于分块每次要向两个方向跑,所以其实只用check一边

这个做法比之前的做法空间,常数,以及代码复杂度都小了很多,可谓是分块之鉴

可以在这里提交https://www.luogu.org/problemnew/show/P5048

P.S:

对于问题1,2,我们目前不知道是否达到了下界,如果大家有了解这个的可以在评论区说一下

对于问题3可以去看range mode query的wiki,上面的论文说有strong evidence suggest这个东西是下界了

2019.9.5 update:其实我们在半年前就做出了$O( n^1.41 )$的区间逆序对,但是8.30被别人先挂了arxiv,所以也没什么意义了吧

2020.4.2 update:看到一篇arxiv上$O( n^1.4851 )$的区间众数

reminder

2017-08-17 01:24:29 By OldDriverTree

关于某神奇的数据结构

等我完全搞清楚了发个博客科普一下吧

共 11 篇博客