https://wiki.cvbbacm.com/ 2026-04-30T02:11:18+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-08-03T23:26:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:%E6%99%AE%E9%80%9A%E8%8E%AB%E9%98%9F%E7%AE%97%E6%B3%95_lgwza&rev=1596468376&do=diff 普通莫队算法 形式 假设 $n=m$，那么对于序列上的区间询问问题，如果从 $[l,r]$ 的答案能够 $O(1)$ 扩展到 $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$ （即与 $[l,r]$ 相邻的区间）的答案，那么可以在 $O(n\sqrt{n})$ 的复杂度内求出所有询问的答案。 实现 离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步步移动即可）。$[l,r]$$l$$r$$n$$c_i$$m$$l$$r$$l$$r$$[l,r]$$l$$r$$O(n)$$[i,i]$$col[i]$$i$$ans$$k$$ans$$C^2_{col[k]+1}-C^2_{col[k]}$$ans$$C^2_{col[k]}-C^2_{col[k]-1}$$\displaystyle\frac{ans}{C^2_{r-l+1}}$$C^2_a=\displaystyle\frac{a(a-1)}{2}$$C^2_{a+1}-C^2_a=\displaystyle\frac{(a+1)a}{2}-\displaystyle\frac{a… text/html 2020-08-01T10:19:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_05_02--2020_05_08_%E5%91%A8%E6%8A%A5&rev=1596248340&do=diff 2020/05/02--2020/05/08 周报 团队训练 姜一凡 专题 dp的优化 比赛 题目 cf639_div1_a_b 蒋贤蒙 专题 centroid_decomposition 比赛 题目 王赵安 专题 线段树 比赛 Codeforces Round #639 (Div. 2) prob:2/4/6 rk:4201/18379 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2021-07-13T23:29:09+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_05_09--2020_05_15_%E5%91%A8%E6%8A%A5&rev=1626190149&do=diff 2020/05/09--2020/05/15 周报 团队训练 比赛时间 比赛名称 赛中过题 总计过题 总题目数 排名 2020.05.09 2020, XIII Samara Regional Intercollegiate Programming Contest 11 12 13 N/A 姜一凡 专题 可持久化线段树 比赛 题目 cf641 蒋贤蒙 专题 重链剖分 比赛 题目 text/html 2021-07-09T21:49:19+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_05_16--2020_05_22_%E5%91%A8%E6%8A%A5&rev=1625838559&do=diff back 2020/05/16--2020/05/22 周报 团队训练 姜一凡 专题 比赛 题目 cf643 蒋贤蒙 专题 lct 比赛 题目 王赵安 专题 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-08-01T10:19:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_05_23--2020_05_29_%E5%91%A8%E6%8A%A5&rev=1596248366&do=diff back 2020/05/23--2020/05/29 周报 团队训练 比赛时间 比赛名称 赛中过题 总计过题 总题目数 排名 2020.05.23 UFPE Starters Final Try-Outs 2020 9 10 11 N/A 姜一凡 专题 比赛 题目 蒋贤蒙 专题 长链剖分 比赛 题目 text/html 2020-08-01T10:19:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_05_30--2020_06_05_%E5%91%A8%E6%8A%A5&rev=1596248373&do=diff back 2020/05/30--2020/06/05 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 可持久化数据结构_1 专题 比赛 题目 王赵安 专题 比赛 Codeforces Round #646 (Div. 2) prob:3/3/6 rk:2811/14073 Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! prob:3/3/6 rk:3156/12044 题目 本周推荐 姜一凡 蒋贤蒙 可持久化数据结构_1 王赵安 text/html 2020-08-01T10:19:40+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_06_06--2020_06_12_%E5%91%A8%E6%8A%A5&rev=1596248380&do=diff back 2020/06/06--2020/06/12 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 咕咕咕 比赛 题目 王赵安 专题 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-08-01T10:19:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_06_13--2020_06_19_%E5%91%A8%E6%8A%A5&rev=1596248388&do=diff back 2020/06/13--2020/06/19 周报 团队训练 姜一凡 专题 dft 比赛 题目 蒋贤蒙 专题 点分树 比赛 题目 王赵安 专题 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-08-01T10:19:56+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_06_20--2020_06_26_%E5%91%A8%E6%8A%A5&rev=1596248396&do=diff back 2020/06/20--2020/06/26 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 替罪羊树 kd_tree 比赛 题目 王赵安 专题 比赛 Codeforces Round #652 (Div. 2) prob:3/4/6 rk:1825/14647 Educational Codeforces Round 90 (Rated for Div. 2) prob:4/4/7 rk:3367/12840 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-08-01T10:20:04+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_06_27--2020_07_03_%E5%91%A8%E6%8A%A5&rev=1596248404&do=diff back 2020/06/27--2020/07/03 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 线性基 数论 1 数论 2 比赛 牛客练习赛66 rk:15/386 Codeforces Round #654 (Div. 2) rk:769 题目 王赵安 专题 数论概论学习小结 欧拉函数 莫比乌斯反演 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-08-01T10:20:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_07_04--2020_07_10_%E5%91%A8%E6%8A%A5&rev=1596248412&do=diff back 2020/07/04--2020/07/10 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 笛卡尔树 线段树合并/分裂 fhq treap 可持久化数据结构 2 左偏树/可并堆 数论 3 比赛 题目 王赵安 专题 树链剖分 线性筛模板 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-08-01T10:20:22+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_07_11--2020_07_17_%E5%91%A8%E6%8A%A5&rev=1596248422&do=diff back 2020/07/11--2020/07/17 周报 团队训练 姜一凡 专题 计算几何 比赛 无 题目 蒋贤蒙 专题 树套树 1 图论 1 图论 2 比赛 无 题目 见专题部分 王赵安 专题 字符串基础 字符串匹配 字符串哈希 字典树(Trie) 前缀函数与 KMP 算法 比赛 无 题目 见专题部分 本周推荐 姜一凡 洛谷p1742 最小圆覆盖模板$n$$m$$n$$x$$G_x$$k$$C_k$$D_k$$[L_{k_i},R_{k_i}]$$-1$$n$$x$$G_x$$x$$[G_x,\inf]$$k$$D_k$$k$$[0,D_k]$$k$$[L_{k_i},R_{k_i}]$$k$$k_i$$[L_{k_i},R_{k_i}]$$i$$i$$i$$10^5$$10^6$$i$$\pi[i]$… text/html 2020-08-01T10:31:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_07_18--2020_07_24_%E5%91%A8%E6%8A%A5&rev=1596249117&do=diff back 2020/07/18--2020/07/24 周报 团队训练 姜一凡 专题 bsgs 比赛 题目 蒋贤蒙 专题 图论 3 矩阵树定理 比赛 无 题目 见专题部分 王赵安 专题 后缀数组 比赛 Codeforces Round #658 (Div. 2) pro:4/5/6 rk:1181/14672 题目 本周推荐 姜一凡 洛谷p3846 分类 BSGS 大致题意 $b^l=n(mod p)$$l$$i$$r_i$$p$$m$$f$$n$$s$$f\gt s,m\lt n$$N$$r_i$$r_i$$0$$\inf$$p$$i$$i+m$$\inf$$f$$i+n$$\inf$$s$$r_i$$r_i$$0$$\inf$$0$$2len$ text/html 2020-07-31T11:05:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_07_25--2020_07_31_%E5%91%A8%E6%8A%A5&rev=1596164712&do=diff back 2020/07/25--2020/07/31 周报 团队训练 姜一凡 专题 polya定理 比赛 题目 蒋贤蒙 专题 树上启发式合并 虚树 CDQ分治 整体二分 比赛 无 题目 见专题部分 王赵安 专题 AC 自动机 比赛 Educational Codeforces Round 92 (Rated for Div. 2) pro:3/3/7 rk:1823/15601 Codeforces Round #660 (Div. 2) pro:3/3/5 rk:1489/13591 题目 本周推荐 $n$$n$$n$$n$$n-1$$k$$P_k$$C(P_k)=gcd(k,n)$$\frac{1}{n}\sum_{k=1}^{n}n^{\gcd(k,n)}$$gcd(k,n)$$\frac{1}{n}\sum_{d|n}n^d\phi(\frac{n}{d})$$O(Tn^{\frac{3}{4}})$$n$$q$$k_i$$k_i$$1$$\text{dp}$$\text{dfs}$$\text{dfs}$$\text{dp}… text/html 2020-08-07T16:31:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_08_01--2020_08_07_%E5%91%A8%E6%8A%A5&rev=1596789094&do=diff back 2020/08/01--2020/08/07 周报 团队训练 姜一凡 专题 半平面交 比赛 无 题目 无 蒋贤蒙 专题 动态规划 1 多项式 1 多项式 2 比赛 无 题目 见专题部分 王赵安 专题 普通莫队算法 状压 DP 数位 DP 比赛 AtCoder Beginner Contest 174 pro:5/6/6 rk:1676/9750 题目 见专题部分 本周推荐 $\text{NTT}$$S$$S$$n$$p$$x$$p\le 8000,n\le 10^9,1\le x\lt p$$p$$1004535809$$p$$g$$S$$p$$x=g^y$$p-1$$y$$f_{i,j}$$i$$j$$f_{i,j}=\sum_{k=0}^j f_{i-1,j-k}f_{1,k}$$\text{NTT}$$p-1$$p-1$$O(np\log p)$$O(p\log p\log n)$$\text{NTT}$$N$$Q$$1\sim N$$\sqrt N$$Q$$l$$l$$r$$r$$Q$$1$$1$… text/html 2020-08-14T14:45:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_08_08--2020_08_14_%E5%91%A8%E6%8A%A5&rev=1597387510&do=diff back 2020/08/08--2020/08/14 周报 团队训练 姜一凡 专题 线性基 比赛 无 题目 无 蒋贤蒙 专题 生成函数 1 多项式 3 生成函数 2 比赛 无 题目 见专题部分 王赵安 专题 匈牙利算法 图匹配 增广路定理 网络流简介 Dinic 算法 类 Dinic 算法 比赛 Codeforces Round #662 (Div. 2) pro:3/4/6 rk:1278/13194 Codeforces Round #663 (Div. 2) pro:3/5/5 rk:1137/13140 $\text{NTT}$$x\in [0,n]$$x=i$$p_i$$x$$[0,x]$$m$$x=i$$f_{k,i}$$k$$x=k$$f_{0,i}=p_i$$$f_{k,i}=\sum_{j=i}^{n} \frac {f_{k-1,j}}{j+1}$$$$ \begin{equation}\begin{split} F_k(x)&=\sum_{i=0}^n f_{k,i}x^i\\ &=\sum_{… text/html 2020-08-21T13:30:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_08_15--2020_08_21_%E5%91%A8%E6%8A%A5&rev=1597987812&do=diff back 2020/08/15--2020/08/21 周报 团队训练 姜一凡 专题 A*搜索 比赛 无 题目 无 蒋贤蒙 专题 树同构 Prufer 序列 拓展域并查集 可持久化数据结构 3 线段树分治 比赛 无 题目 见专题部分 王赵安 专题 最小割 一般图最大匹配 比赛 题目 本周推荐 姜一凡 洛谷p1379 标签 A*搜索 题意 $g(n)$$n$$1\sim n$$v_i$$m$$s$$v$$l,r,d,x$$x$$t$$[l,r]$$[t-d+1,t]$$0$$O(\log v)$$O((n+m)\log v)$$O((n+m)\log v\log m)$$n*m$$(i,j)$$s$$t$$(i,j)$$(i+1,j)$$w$$x$$s$$x$$w$$x$$(i,j)$$(i+1,j)$$INF$… text/html 2020-08-28T17:13:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_08_22--2020_08_28_%E5%91%A8%E6%8A%A5&rev=1598606029&do=diff back 2020/08/22--2020/08/28 周报 团队训练 姜一凡 专题 虚树 比赛 题目 蒋贤蒙 专题 二项式反演 斯特林数 多项式 4 字符串 1 比赛 无 题目 无 王赵安 专题 Splay 2-SAT 比赛 题目 本周推荐 姜一凡 洛谷p2495 题目大意 给定一棵树， $m$ 个询问，每次询问 $k$$1$$dp[now]$$dp[now]=\left\{ \begin{aligned}edge[now][fa].w,target[now]=true \\ \sum dp[v],now=1\\min(\sum dp[v],edge[now][fa].w),others\end{aligned} \right.$$[L+1]\times n$$(u_1,v_1)\to (u_2,v_2)$$w_{v_1,v_2}$$(0,x)$$(\ast,y)$$\ast$$m$$0\le t\lt k$$m\equiv t\pmod k$$p$$p$$10^8\le p\le 2^{30},k\mid p-1,1\le k… text/html 2020-09-04T18:07:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_08_29--2020_09_04_%E5%91%A8%E6%8A%A5&rev=1599214052&do=diff back 2020/08/29--2020/09/04 周报 团队训练 姜一凡 异或方程组 专题 比赛 题目 蒋贤蒙 专题 字符串 2 字符串 3 字符串 4 比赛 题目 王赵安 专题 可持久化数组 主席树 拆点 比赛 题目 本周推荐 姜一凡 洛谷p2447 标签 异或方程组 解析 异或方程组的模板题$n$$n$$\text{LCS}$$\text{SAM}$$\text{SAM}$$ch[pos][c]$$+1$$\text{parent}$$\text{parent}$$ch[pos][c]$$ch[pos][c]$$len_\text{pos}+1$$|T|$$O(1)$$O(|S|)$$n$$\text{SAM}$$\text{SAM}$$\text{parent}$$O(\sum |S|)$$n$$a_i,b_i,c_i$$1\le n\le 5\times 10^5$$O(n\log n)$… text/html 2020-09-10T21:56:45+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_09_05--2020_09_11_%E5%91%A8%E6%8A%A5&rev=1599746205&do=diff back 2020/09/05--2020/09/11 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 数据结构练习 1 比赛 题目 王赵安 专题 杜教筛 虚树 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-09-17T14:07:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_09_12--2020_09_18_%E5%91%A8%E6%8A%A5&rev=1600322877&do=diff back 2020/09/12--2020/09/18 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 比赛 CCPC Wannafly Winter Camp Day1 题目 王赵安 专题 拉格朗日插值 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-09-24T22:21:06+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_09_19--2020_09_25_%E5%91%A8%E6%8A%A5&rev=1600957266&do=diff back 2020/09/19--2020/09/25 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 数论 4 比赛 题目 王赵安 专题 博弈论 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-10-02T13:55:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_09_26--2020_10_02_%E5%91%A8%E6%8A%A5&rev=1601618138&do=diff back 2020/09/26--2020/10/02 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 吉司机线段树 线性基(更新) 比赛 题目 王赵安 专题 Manacher 算法 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-10-08T15:17:11+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_10_03--2020_10_09_%E5%91%A8%E6%8A%A5&rev=1602141431&do=diff back 2020/10/03--2020/10/09 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 线段树分治（更新） 左偏树/可并堆（更新） 重构树 比赛 2020牛客国庆集训派对 题目 王赵安 专题 回文树 序列自动机 比赛 题目 本周推荐 姜一凡 蒋贤蒙 洛谷p3261 标签 左偏树 题意 $1$$(h_i,a_i,v_i)$$m$$s_i$$c_i$$i$$j$$c_i\lt h_j$$a_i=0$$v_i$$a_i=1$$v_i$$\text{long long}$$a_i=1$$v_i\gt 0$$\text{dfs}$$c\lt h$$a_i=1$$v_i\gt 0$$(n\log m)$$O(m\log m)$$O(n)$$O((n+m)\log m)$… text/html 2020-10-16T09:57:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_10_10--2020_10_16_%E5%91%A8%E6%8A%A5&rev=1602813449&do=diff back 2020/10/10--2020/10/16 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 比赛 Educational Codeforces Round 96 题目 王赵安 专题 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2021-09-04T21:48:41+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:2020_10_17--2020_10_23_%E5%91%A8%E6%8A%A5&rev=1630763321&do=diff back 2020/10/17--2020/10/23 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 数论 5 多项式练习 1 比赛 Codeforces Raif Round 1 (Div. 1 + Div. 2) 题目 王赵安 专题 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-07-29T11:17:06+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:ac_%E8%87%AA%E5%8A%A8%E6%9C%BA_lgwza&rev=1595992626&do=diff AC 自动机 概述 AC 自动机是以 Trie 的结构为基础，结合KMP 的思想建立的。 简单来说，建立一个 AC 自动机有两个步骤： * 基础的 Trie 结构：将所有的模式串构成一棵 Trie。 * KMP 的思想：对 Trie 树上所有的结点构造失配指针。$s_1,s_2,\cdots,s_n$$Q$$u$$v$$v\in Q$$v$$u$$u$$u$$p$$p$$u$$trie[p,c]=u$$u$$trie[fail[p],c]$$u$$trie[fail[p],c]$$p$$fail[p]$$u$$fail[u]$$trie[fail[p],c]$$trie[fail[fail[p]],c]$$fail[u]$$u$$fail[5]=10$$fail[10]=0$$fail[6]=7$$trie[u,c]$$u$$trans(u,c)$$u$$fail[u]$$u$$trans[u][i]$$trans[u][i]$$trans[fail[u]][i]$$trans[u][i]$$trans[fail[u]][i]$$S$$trans[S][c]$$S$$S…