immix's blog

约定下标从 0 开始。 Z 函数 定义 z[i]z[i]z[i] 表示字符串 sss 和 s[i..]s[i..]s[i..]（即从 iii 开始的部分）的最长公共前缀。 我们可以在 O(n)O(n)O(n) 复杂度内计算出一个字符串的 Z 函数。（当然也可以哈希单 log 完成） 假设我们已经求出了 z[0],z[1],…,z[i−1]z[0],z[1],\ldots,z[i-1]z[0],z[1],…,z[i−1]，对于每个 iii，将 [i,i+z[i]−1][i,i+z[i]-1][i,i+z[i]−1] 称为它的 Z-box。 我们找出 1∼i−11\sim i-11∼i−1 中右端点最靠右的 Z-box，记作 [l,r][l,r][l,r]。（初始时 l=r=0l=r=0l=r=0，不计 z[0]z[0]z[0] 的 Z-box） 分类讨论： i≤ri\le ri≤r：根据 Z 函数定义可知 s[0..r−l]=s[l,r]s[0..r-l]=s[l,r]s[0..r−l]=s[l,r]，则 s[i..r]=s[i−l,r−l]s[i..r]=s[i-l,r-l]s[i. ...

包括删边，删点，修改边权，加边，查询最短路一类问题。 一般图多源最短路 一般图的多源的删边最短路由于受到 Floyd O(n3)O(n^3)O(n3) 的限制，做法一般比较单一。 删边，多源最短路 题目 ABC375F Road Blocked 给定一个有 nnn 个点，mmm 条边的带权无向图，有 qqq 个查询，类型如下： 1 i：删除第 iii 条边； 2 x y：求 xxx 到 yyy 的最短路长度（无法到达输出 -1）。 数据范围：n≤300,m≤(n2)n\le 300, m\le \binom n 2n≤300,m≤(2n​)，删边不超过 300300300 次。 解法 看到删边不超过 300300300 次启发我们使用 Floyd O(n3)O(n^3)O(n3) 解决这个问题。Floyd 能处理新加入一条边，但是比较难做删边，所以我们离线之后倒过来处理，就只需要加边和求任意两点最短路。 怎么用 Floyd 更新一条边对多源最短路的贡献？ 假设这条边是 (u,v)(u, v)(u,v)，长度为 www，di,jd_{i,j}di,j​ 表示 i,ji,ji,j 之间 ...

概述 目标 由于修改过一次 permalink，但没有设定重定向，导致之前的链接会出现 404 问题。 _config.yml12- permalink: :year/:month/:day/:title/+ permalink: posts/:hash/ 我们希望能够添加一个搜索链接，让用户搜索找到新的页面。 效果图： 需要修改的文件 themes\butterfly\layout\includes\404.pug（用于修改 404 页面内容） themes\butterfly\source\js\search\local-search.js（用于自动填入搜索内容） 修改 404 页面 themes\butterfly\layout\includes\404.pug1234567891011121314151617181920212223242526272829303132333435363738394041- var top_img_404 = theme.error_404.background || theme.default_top_img#body-wrap.er ...

提供一个比较好写的 1 log 做法。 题意 有 nnn 个桶，容积无限大，知道每个桶初始有 aia_iai​ 千克的水。现在有一个桶恰额外含有 0.1790.1790.179 千克的毒药，进行任意次如下两种操作： 选择两个桶 AAA，桶 BBB，比较重量，知道哪边重或一样重； 选择桶 AAA，桶 BBB，从 AAA 桶中倒 xxx 千克水（xxx 不一定是整数）进入 BBB 桶，要求： ※ AAA 桶必须不含毒药； ※ AAA 桶至少要含有 xxx 千克的水。 判断是否能唯一确定哪个桶装着毒药，输出 Yes/No。 现在会进行 qqq 次修改，每次的修改为增加一个初始水量为 bbb 的桶，或删去一个初始水量为 bbb 的桶（保证存在），修改持续。 每次修改后，输出 Yes/No，代表当前情况是否能判断哪个桶装着毒药。 n,q≤2×105,ai,b≤106n,q\le 2\times 10^5, a_i,b\le10^6n,q≤2×105,ai​,b≤106。 解法 注意到操作 1 只有两个桶装的水是同样重的才有用（要不然有没有毒药不会影响结果），而且操作 2 选择的桶 AAA 一 ...

题意 LOJ6077 「2017 山东一轮集训 Day7」逆序对 给定 n,kn,kn,k，求长度为 nnn 的逆序对数恰为 kkk 的排列个数，对 109+710^9+7109+7 取模。 n,k≤105n,k\le 10^5n,k≤105。 生成函数做法 先考虑一个 O(nk)O(nk)O(nk) 的朴素 dp。考虑按照位置一个一个插入数，假设当前插入第 iii 个数，根据插入的数与前面的数的大小，可以构成 [0,i−1][0,i-1][0,i−1] 个逆序对。 设 dpi,jdp_{i,j}dpi,j​ 表示长度为 iii 的有 jjj 个逆序对的排列数量： dpi,j=∑max⁡(0,j−i+1)≤k≤jdpi−1,kdp_{i,j} = \sum_{\max(0,j-i+1)\le k\le j}dp_{i-1,k} dpi,j​=max(0,j−i+1)≤k≤j∑​dpi−1,k​ 用前缀和就可以做到 O(nk)O(nk)O(nk) 了。 我们考虑写出这个问题的生成函数，xpx^pxp 的系数表示逆序对个数为 ppp 的排列个数。 一开始 F1=1F_1 = 1F1​=1， ...

其实是 有关区间的三个经典贪心算法（前两个）的树上版本。 等价性 问题 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 ...