immix's blog

其实是 有关区间的三个经典贪心算法（前两个）的树上版本。 等价性 问题 1：给定一棵树，和 mmm 条路径，求最少选几个点，使得每个路径上都至少有一个点。 问题 2：给定一棵树，和 mmm 条路径，求最多选出几个路径，使得任意两个路径不存在公共点。 下证明：这两个问题的答案相等。 类比区间时候的证明，设问题 1 答案为 xxx，问题 2 答案为 yyy，易证 x≥yx\ge yx≥y。 接下来证明能用 yyy 个点覆盖完所有路径。用反证法，假设存在一个至少有 y+1y+1y+1 个点的最佳答案，对于 yyy 个不相交路径上面每个都至少有一个点，第 y+1y+1y+1 个点如果在某个不相交路径内部，说明我们可以多选出一个不相交路径，在外部同理，矛盾，因此两个问题答案相同。 后面我们会分别从两个角度出发介绍两种算法，这两种算法都可以用来解决这两个题目。 算法 1（贪心，从树上用最少点覆盖路径角度出发） 求出答案 直接贪心。求出每个路径的顶点（也就是两个端点的 LCA），按照从深到浅的顺序一个一个取，如果已经被之前的点覆盖了就跳过。 证明： 根据归纳，我们只需要证明对于任意情况，选择最深 ...

问题 1 题目 CF911G. Mass Change Queries 给定长度为 nnn 的序列，有 qqq 个操作，每个操作是把区间 [l,r][l,r][l,r] 中等于 xxx 的数改成 yyy。 输出 qqq 步操作完的数列。 n,q≤2×105,ai≤100n,q\le 2\times 10^5,a_i\le 100n,q≤2×105,ai​≤100。 做法 （这个问题有用动态开点线段树的做法，但是线段树难以解决区间询问问题，我们这里介绍分块做法。） 考虑分块，块长为 BBB，用并查集维护每个数的位置，维护每个块每个颜色的代表元素 rti,xrt_{i,x}rti,x​（如果没有就是 000），并保证 a[rti,x]a[rt_{i,x}]a[rti,x​] 始终对应其真实颜色，空间复杂度 O(V⋅nB)O\left(V\cdot \dfrac n B\right)O(V⋅Bn​)。 修改整块，把 xxx 变 yyy 的时候： 如果 xxx 是空的就是什么都不做； 否则： 如果 yyy 是空的，执行 rti,y←rti,xrt_{i,y}\leftarrow rt_{i ...

QOJ# 9904. 最小生成树 题意 给定一个有 nnn 个节点的无向完全图、序列 a3∼a2n−1a_3\sim a_{2n-1}a3​∼a2n−1​，边 (i,j)(i,j)(i,j) 的边权为 ai+ja_{i+j}ai+j​，求该图最小生成树的权。 分析 看到最小生成树考虑采用 Kruskal, Prim, Boruvka 的一种。 这道题采用 Kruskal 即可。 根据 Kruskal 的过程，每次取出最小的 aka_kak​，连上所有可能的边。我们考虑如何快速求出每个 aka_kak​ 的贡献。 做法 1（二分） 根据均摊我们知道，总共只会连上 n−1n-1n−1 条边。 如果我们能够花费一定的代价，快速求出下一个能连上的边，就能解决本题。 采用并查集，维护一个序列，每个位置的值是它在并查集中的代表元素。 假设当前处理的是 aka_kak​，每次连接的是以 k/2k/2k/2 为中心的一个区间，如果 [l,r] (l+r=k)[l,r]\ (l+r=k)[l,r] (l+r=k) 内的都已经连上了，反映在序列中就是 [l,r][l,r][l,r] 是回文串，而这个显然是 ...

子序列指的是不连续的一些位置组成的序列，而子串指的是连续的一段区间。 括号串的简化 一个括号序列能匹配都匹配完之后剩下一定是一段前缀 ) 和后缀 (。（要不然就还有能匹配的部分） 比如序列 (())))()(() 最后留下的就是 ))(。 而我们能证明，该括号序列的最长合法子序列就是删掉了留下来的字符所得到的结果。（这就是答案的上界，而我们取到了上界） 比如说，上面的序列最长合法子序列就是 (())()()。 我们尝试把这种结构放到线段树上维护。 区间翻转，区间最长合法括号子序列 P10513 括号 给定一个长度为 nnn 的括号序列，支持 mmm 次操作： 翻转 [l,r][l,r][l,r] 中的括号，即 ( 变 )，) 变 (。 查询子串 [l,r][l,r][l,r] 最长合法括号子序列的长度除 222。 n,m≤5×105n,m\le 5\times 10^5n,m≤5×105。 对于线段树的每个节点，我们维护当前在左边剩余的右括号（l），右边剩余的左括号（r），节点的合并就是把中间的括号的一边匹配完。 1234567struct Node{ // 形如 ))) ...

准确的来说，线性基这个概念可以扩展到更大的线性空间中，但本文只包括了异或线性基。 线性基 定义 对于一个序列来说，一个满足如下条件的集合称作其线性基（不唯一）： 线性基中任意选择一些数（可以不选）的异或值所构成的集合，与原序列中任意选择一些数的异或值所构成的集合相同。 该集合的元素个数最少。 比如对于序列 {1,4,5,7}\{1,4,5,7\}{1,4,5,7} 来说，其一个线性基就是 {1,3,4}\{1,3,4\}{1,3,4}。 性质 线性基中不存在取值集合，使得异或和为 000。 否则可以删去一个数，仍然可以表达出一样的集合。 线性基中不存在任意两组取值集合，使得异或和相等。 否则就能得到异或和为 000 的取值集合。 若线性基的大小为 SSS，能异或出的数（包括不选得到 000）个数为 2S2^S2S。 由性质 2 可知任意异或都不重复，故个数为 2S2^S2S。 建立线性基 贪心算法 假设当前插入的数是 xxx，我们的线性基为 b0,b1,…,bkb_0,b_1,\ldots,b_kb0​,b1​,…,bk​，初始都为 000。 从高到低扫，如果 xxx 第 pp ...

前言 前置知识： 阶、原根、离散对数; 多项式（1）— 快速傅里叶变换（FFT）。 FFT 已经能很好的在 O(nlog⁡n)O(n\log n)O(nlogn) 内解决卷积问题，但是 FFT 用到的单位根和三角函数有关，只能采用浮点数储存，必定会带来精度误差。 我们尝试不在复数域内，而是在模剩余系内寻求一种新的单位根来解决问题，这样带来了两个好处： 不再有误差（只要大小没有超出模数）； 如果题目要求取模，一并可以完成取模的任务。 新型单位根 我们回看 FFT，FFT 中单位根 wnkw_n^kwnk​ 满足了如下性质： wnk=(wn1)kw_n^k = \left(w_n^1\right)^kwnk​=(wn1​)k； wn0,wn1,…,wnn−1w_n^0,w_n^1,\ldots,w_n^{n-1}wn0​,wn1​,…,wnn−1​ 互不相同； wnk+n/2=−wnkw_n^{k+n/2}=-w_n^kwnk+n/2​=−wnk​； 这个性质可以导出 wnk mod n=wnkw_n^{k\bmod n}=w_n^kwnkmodn​=wnk​。 w2n2 ...

多项式乘法与卷积 对于两个多项式 f(x)=∑i=0naixi,g(x)=∑i=0nbixif(x)=\sum_{i=0}^na_ix^i,g(x)=\sum_{i=0}^nb_ix^if(x)=∑i=0n​ai​xi,g(x)=∑i=0n​bi​xi，如果要求出乘积多项式 fgfgfg，朴素实现是 O(n2)O(n^2)O(n2) 的。但是，利用 FFT，我们可以在 O(nlog⁡n)O(n\log n)O(nlogn) 时间内完成这一问题。 从另一个角度来理解，多项式的乘法是一种加法卷积。 对于两个序列 {a0,a1,…,an},{b0,b1,…,bn}\{a_0,a_1,\ldots,a_n\},\{b_0,b_1,\ldots,b_n\}{a0​,a1​,…,an​},{b0​,b1​,…,bn​}，定义其卷积 {c0,c1,…,c2n}\{c_0,c_1,\ldots,c_{2n}\}{c0​,c1​,…,c2n​}，ck=∑i+j=kaibjc_k = \sum_{i+j=k}a_ib_jck​=∑i+j=k​ai​bj​。 不难发现 {an},{bn}\{a_n\},\{ ...

欧拉函数 定义 φ(n)\varphi(n)φ(n) 表示 1∼n1\sim n1∼n 中与 nnn 互质的数个数。 形式化地讲， φ(n)=∑i=1x[gcd⁡(i,n)=1]\varphi(n)=\sum_{i=1}^{x}[\gcd(i,n)=1]φ(n)=∑i=1x​[gcd(i,n)=1]，其中 [⋅][\cdot][⋅] 表示艾佛森括号。 性质 1 φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}φ(pk)=pk−pk−1，其中 ppp 为质数。 证明： 1∼pk1\sim p^k1∼pk 中恰有 pk−1p^{k-1}pk−1 个 ppp 的倍数，只有他们与 pkp^kpk 不互质。 即 φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}φ(pk)=pk−pk−1。 性质 2 欧拉函数是积性函数。 也就是说，对于互质 a,ba,ba,b，φ(ab)=φ(a)φ(b)\varphi(ab)=\varphi(a)\varphi(b)φ(ab)=φ(a)φ(b)。 证明： 引理1：xxx 与 ababab 互质的充要条件是 x ...

离散变量取值问题 有若干个变量，每个变量取值为 v1,v2,…,vnv_1,v_2,\ldots,v_nv1​,v2​,…,vn​，现在要求所有变量的和最小（大），且不同变量的取值有某种限制。（详细见下文例题） 先不考虑限制，考虑用最小割刻画这个问题。 如图所示，对每一个变量都建立 n+1n+1n+1 个点 X1,X2,…,Xn+1X_1, X_2, \ldots, X_{n+1}X1​,X2​,…,Xn+1​： 从 SSS 到 X1X_1X1​ 建立一条边权为 ∞\infty∞ 的边； 从 Xn+1X_{n+1}Xn+1​ 到 TTT 建立一条边权为 ∞\infty∞ 的边； 从 XiX_{i}Xi​ 到 Xi+1X_{i+1}Xi+1​ 建立一条边权为 viv_{i}vi​ 的边； 从 Xi+1X_{i+1}Xi+1​ 到 XiX_{i}Xi​ 建立一条边权为 ∞\infty∞ 的边。 这样我们保证了，每个变量所构造出的一条链上，在最小割中有且仅有一条边被割掉，被割掉的边的边权就代表了我们为这个变量的取值。 证明： 存在性： 如果没有边被割，那么显然存在 S→TS\to ...

题意 [ARC068E] Snuke Line 给定 nnn 个区间 [li,ri] (1≤li≤ri≤m)[l_i,r_i]\ (1\le l_i \le r_i \le m)[li​,ri​] (1≤li​≤ri​≤m)。 对 1∼m1\sim m1∼m 中的每一个 iii，求出存在一个 iii 的倍数在其中的区间个数。 解法 1（整除分块） 我们发现，对于一个 ddd 来说，[l,r][l,r][l,r] 中有 ddd 的倍数的充要条件是 ⌊l−1d⌋≠⌊rd⌋\left \lfloor \dfrac{l-1}{d} \right \rfloor \neq \left \lfloor \dfrac{r}{d} \right \rfloor⌊dl−1​⌋=⌊dr​⌋。 略证： （引理）⌈xy⌉=⌊x−1y⌋+1\left \lceil \dfrac{x}{y} \right \rceil = \left \lfloor \dfrac{x-1}{y} \right \rfloor +1⌈yx​⌉=⌊yx−1​⌋+1。 证明：设 x=ky+bx=ky+bx=ky+b，其中 ...