BZOJ-3509. [CodeChef] COUNTARI

给定一个长度为 n ~(1 \leq n \leq 10^5) 的数组 a_i~(0 \leq a_i \leq 3\cdot 10^4),问有多少对 (i, j, k) 满足 i < j < ka_i - a_j = a_j - a_k

也就是统计有多少对长度为 3 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI

例如 3 5 3 6 3 4 10 4 5 2,就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对

(more…)

Read More

从多项式乘法到快速傅里叶变换

概述

计算多项式的乘法,或者计算两个大整数的乘法是在计算机中很常见的运算,如果用普通的方法进行,复杂度将会是 \mathcal O(n^2) 的,还有一种分治乘法,可以做到 \mathcal O(n^{\log_23}) 时间计算(可以看这里)。下面从计算多项式的乘法出发,介绍快速傅里叶变换(Fast Fourier Transform, FFT)如何在 \mathcal O(n\log n) 的时间内计算出两个多项式的乘积。另外,存在只需要两次快速傅立叶变换就可以计算大整数乘法的方法,具体见实序列离散傅里叶变换的快速算法

准备知识

这里介绍一些后面可能会用到的知识(主要是关于多项式、卷积以及复数的),如果你已经知道觉得它太水了或者想用到的时候再看就跳过吧

多项式

简单来说,形如 a_0+a_1X+a_2X^2+\cdots+a_nX^n 的代数表达式叫做多项式,可以记作P(X)=a_0+a_1X+a_2X^2+\cdots+a_nX^na_0, a_1, \cdots, a_n 叫做多项式的系数X 是一个不定元,不表示任何值,不定元在多项式中最大项的次数称作多项式的次数

多项式的系数表示法

像刚刚我们提到的那些多项式,都是以系数形式表示的,也就是将 n 次多项式 A(x) 的系数 a_0, a_1, \cdots, a_n 看作 n+1 维向量 \vec a=(a_0,a_1,\cdots,a_n),其系数表示(coefficient representation)就是向量 \vec a

多项式的点值表示法

如果选取 n+1不同的数 x_0, x_1, \cdots, x_n 对多项式进行求值,得到 A(x_0), A(x_1), \cdots, A(x_n),那么就称 \{\left(x_i, A(x_i)\right) : 0 \leq i \leq n, i \in \mathbb Z\} 为多项式 A(x)点值表示(point-value representation)

多项式 A(x) 的点值表示不止一种,你只要选取不同的数就可以得到不同的点值表示,但是任何一种点值表示都能唯一确定一个多项式,为了从点值表示转换成系数表示,可以直接通过插值的方法

复数

后面提到的 i,除非作为 \sum 求和的变量,其余的都表示虚数单位 \sqrt{-1}

单位根

n 次单位根是指能够满足方程 z^n=1 的复数,这些复数一共有 n 个它们都分布在复平面的单位圆上,并且构成一个正 n 边形,它们把单位圆等分成 n 个部分

根据复数乘法相当于模长相乘,幅角相加就可以知道,n 次单位根的模长一定是 1,幅角的 n 倍是 0

这样,n 次单位根也就是

e^{\frac{2\pi ki}{n}}, k = 0, 1, 2, \cdots, n - 1

再根据欧拉公式

e^{\theta i}=\cos\theta + i\sin\theta

就可以知道 n 次单位根的算术表示

如果记 \omega_n=e^{\frac{2\pi i}{n}},那么 n 次单位根就是 \omega_n^0, \omega_n^1, \cdots, \omega_n^{n-1}

多项式的乘法

给定两个多项式 A(x), B(x)

 A(x) = \sum_{i=0}^na_ix^i = a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 \\ B(x) = \sum_{i=0}^nb_ix^i = b_nx^n+b_{n-1}x^{n-1}+\cdots+b_1x+b_0

将这两个多项式相乘得到 C(x) = \sum_{i=0}^{2n}c_ix^i,在这里

c_i=\sum_{j+k=i,0\leq j,k\leq n}a_jb_kx^i

如果一个个去算 c_i 的话,要花费 \mathcal O(n^2) 的时间才可以完成,但是,这是在系数表示下计算的,如果转换成点值表示,知道了 A(x), B(x) 的点值表示后,由于只有 n+1 个点,就可以直接将其相乘,在 \mathcal O(n) 的时间内得到 C(x) 的点值表示

如果能够找到一种有效的方法帮助我们在多项式的点值表示和系数表示之间转换,我们就可以快速地计算多项式的乘法了,快速傅里叶变换就可以做到这一点

(more…)

Read More

BZOJ-3771. Triple

这题挺有意思的,来源是 SPOJ-TSUM,题意大概是,给出 n 个物品,第 i 个物品的价值为 x_i(0 < x_i \leq 4\cdot10^4),问在这 n 个物品中选出 1 个或 2 个或 3 个价值和是多少,对于每个价值求出方案个数,在这题中 (a, b)(b, a) 算作一种方案

例如有三个物品

x_1 x_2 x_3
1 2 3

选一个就可以得到 1, 2, 3 三种价值

选两个就可以得到 1+2, 1+3, 2+3 三种价值

选三个就可以得到 1+2+3 一种价值

所以最后答案就是

价值 1 2 3 4 5 6
方案数 1 1 2 1 1 1

(more…)

Read More

BZOJ-2001. [HNOI2010]City城市建设

题目给定一个有 n 个节点,m 条边的有向图,以及 q 个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,n\leq 20000, m \leq 50000, q \leq 50000

看了这篇题解才会做的QAQ

题目核心思想是分治以及缩小图的规模,有两个操作

Contraction:删除必须边

把待修改的边标记成 -\infty,然后跑一次最小生成树,显然这时候出现在生成树中非 -\infty 的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边

Reduction:删除无用边

把待修改的边标记成 \infty,然后跑一次最小生成树,没出现在生成树中的非 \infty 边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,\infty 边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治

然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)

(more…)

Read More

区间K小问题

Problem 1:无修改、无插入区间第K小问题

关于这题,可以直接用主席树(函数式线段树)来解决

假设现在有无限的内存和时间,可以对每个前缀构造一棵权值线段树,然后每次询问区间 [l, r] 就找出前缀 [0, l - 1] 和 [0, r] 的线段树,相减就可以得到所需要的权值线段树,然后在这上面根据子树大小跑就可以了

由于空间有限,最开始不初始化整棵树,而是动态的添加节点,并且在插入的时候只有经过的那一条链上的东西会被更改,所以对于一些没有修改的子树,直接用指针指向上一次的版本,因为每一次插入最多经过 \mathcal O(\log n) 个节点,这样总共空间不会超过 \mathcal O(n\log n),同样,时间复杂度也是每次 \mathcal O(\log n)

参考问题:BZOJ-2588: Spoj 10628. Count on a tree

Problem 2:带修改、无插入区间第K小问题

现在需要修改权值,如果暴力修改每棵线段树的话,最多会要修改 \mathcal O(n) 级别的东西,复杂度也会退化

这时候想想,我们需要的操作是修改一个区间的线段树和询问一个区间的线段树的信息,也就是区间修改和区间查询,很容易会想到树状数组!它能够把每个区间用 \mathcal O(\log n) 个区间来表示出来

所以只要在每个树状数组的节点建立可以权值线段树,表示这个区间的权值信息就可以完成所需要的操作了,时间和空间复杂度都是 \mathcal O(n\log^2 n)

参考问题:BZOJ-1901: Zju2112 Dynamic Rankings

Problem 3:带修改、带插入区间第K小问题

现在我们需要支持可以在某个位置插入一个值,比如原先的序列是 1 2 3,然后在第二个位置插入 4 的话,序列就会变成 1 4 2 3

因为树状数组不支持插入元素,但是类似 Problem 2 的思想,你或许会想到使用平衡树,它也在 \mathcal O(\log n) 的时间内支持区间修改、查询,而且还支持插入元素

也就是平衡树上的节点就表示整棵子树中信息的权值线段树,但是仔细想就会发现,平衡树基本都是需要旋转来维持平衡的,这样一转,对权值线段树修改的时间复杂度就会迅速增大!

替罪羊树(Scapegoat Tree)是一种很神奇的平衡树,它不需要旋转来保持平衡,而是有一个平衡因子 \alpha \in [0.5, 1] 每次插入如果发现某棵子树太不平衡,就把整棵子树暴力重构成完全二叉树

具体来说也就是如果某棵子树满足 \alpha \cdot size > \max (left\_size, right\_size),就认为是不平衡的,然后就重构它

\alpha = 0.5 的时候,这棵树就是完全二叉树,当 \alpha = 1 的时候就永远不会重构,很显然,\alpha 越小,询问的效率越高,\alpha 越大,插入的效率越高

可以证明,替罪羊树的查询效率是 \mathcal O(\log n),而插入均摊 \mathcal O(\log n)

这样,这个问题只需要用替罪羊树再套上权值线段树就可以解决了

但是有一个问题就是你需要动态分配内存,并且在重构的时候要及时释放无用内存。并且在写权值线段树的时候不要写成函数式线段树那样,否则内存会爆(我就不小心写成这样被坑了好久)

参考问题:BZOJ-3065: 带插入区间K小值

Read More