基于 WIDA XCPC 模板，在此基础上对其补充和优化
图论
LCA 最近公共祖先
倍增 LCA
1234567891011121314151617181920212223242526272829303132333435vector<int> dep(n + 1), p(n + 1);auto dfs1 = [&](auto&& self, int fa, int u) ->void { dep[u] = dep[fa] + 1; p[u] = fa; for(int v : gra[u]) if(v != fa) { self(self, u, v); }};dfs1(dfs1, 0, S);int MX = __lg(2*n - 1);vector<vector<int>> st(n + 1, vector<int>(MX + 1));for(int i=1; i<=n; i++) st[i][0] = p[i];for(int j=1; j<=MX ...
前言
仓颉是一个新兴的国产编程语言，由华为自主研发，集百家之长，目前虽是仓颉生态的早期阶段，但已有一批移动应用使用仓颉开发，感觉有不错的前景
一直以来，我都认为写一门编程语言的解释器是一个相当底层的事情，需要借助相当底层的编程语言和工具，实则不然，要知道，C++ 的编译器就是用 C++ 来实现的 (这称之为自举)。因而使用高级语言，完全可以实现一门简单编程语言的解释器。这个项目使用仓颉实现了 Eloquent JavaScript 中介绍的 egg 语言解释器
借助此项目，学习仓颉基础语法和解释器实现思路。将学习过程写成此笔记，梳理思路加深印象
egg 编程语言
基本语法
Egg 语法特征类似 lisp，都是 (xxx … ) 的形式，无论是进行求值，还是定义或调用函数
表达式求值 (op arg1 arg2 ...)
这类似前缀表达式的形式，但不同层需用括号区别，例如计算 (2 * (1 + 3)) 应写为 (* 2 (+ 1 3))
创建函数 (fun (param1 param2 ...) body)
创建函数，如实现 a + b 的函数 (fun (a b) (+ a b ...
XCPC
未读牛客寒假集训营 4 D-数字积木 题解
题意
给定 n 个节点的树，点权构成一个 [0, n) 的排列，求所有连通块的 mex 权值和
思路
将 mex 权值和 转化为 连通块计数。具体来说，分别统计包括 {0}，{0, 1} … {0,…,n-1} 的连通块个数，求这些个数之和就等价于求所有连通块的 mex 权值和。
举个例子，若我们有一个 mex=4 的连通块 S，包括 {0, 1, 2, 3, (mex=4), …} 这些数字。当我们统计包括 {0} 的连通块的个数时，S 会贡献 1，然后是统计 {0, 1}，{0, 1, 2}，{0, 1, 2, 3}，S 也都会贡献 1，一共贡献了 4，正好和其 mex 权值相同
dp 进行连通块计数
令 dp[i] 为 i 必选，i 的子树的连通块个数，每个子节点可选可不选，转移方程为
更新集合贡献
若上一次的必选集合是 {0, 1, 2 … x}，贡献是 lst
现在我们要将 x+1 加入集合，我们从 x+1 开始，不断的向上直到遇到已经必选的点，更新贡献
这样就将经过的点都变成了必选点，之后更新 ans，ans += lst
时间复 ...
XCPC
未读前言
刷刷某大佬整理的区域赛铜牌题题单 (十分之感谢!)
记录一下知识，顺便梳理思路
BA - BZ
BA - The Only Way to the Destination
难度: 2.5
问，任意两方块是否有唯一的简单路径。
思路
首先特判 n = 1 的情况，一定满足，一开始忘判了
n >= 2，发现存在 2 × 2 的方格就不能满足条件，而由于墙的列数不会很多(k ≤ 1e5)，所以 m ≤ 1e9 其实是诈骗，m > 3k 就肯定会有并列的两个空行，一定无法满足条件。此外，可以想象，若存在某个墙组成的连通块不和边界相连，则一定是因为某个路径将其包围，形成了一个环，这种情况一定不满足。
若合法，则一定有 m < 3k，于是我们可以枚举列，判断是否存在 2 × 2 的情况。判断墙是否和边界连通，可以对墙建图后 dfs
整体感觉不是很好写，比较考验码力
另外还要注意，墙是 8 连通而不是 4 连通
MYCODE
12345678910111213141516171819202122232425262728293031323334353637383940414243 ...
为文章封面添加加载动画
把白板换成了一个可爱的加载动画，如下图
难点在我终于找到监测 pjax 换页的方法，使用 history.pushState 就可以
在 themes/anzhiyu/source/js 里新建 cover_loading.js，加入下面代码
1234567891011121314151617181920212223// 自定义事件 , 监测 url 改变 (pjax)(function() { const _pushState = history.pushState; history.pushState = function(...args) { _pushState.apply(this, args); window.dispatchEvent(new Event('urlchange')); };})();const loadingImg = 'https://cdn.amiracle.site/loading.gif';function setloadingImg() { const covers ...
差分约束系统
n 个未知量 x1, x2 ⋯ xn，m 个不等式条件 这样的一组不等式就是一个差分约束系统，差分约束系统的求解可以巧妙的转化为最短路问题
和最短路的关系
先移项，得到 ，可以发现和最短路中的三角不等式非常相似，。因而可以转化成最短路问题，具体来说，先对不等式建图，每个不等式都可看成边，让 j 向 i 连一条权为 c 的边，此图上跑最短路，得到的 disi 就是一组满足条件的解。
转化的充要性证明
限制条件转化为有向边，跑最短路得到的 dis 满足 ，把 disu, disv 看成 xu, xv 的话，也就是 ，因而当最短路有解，也就是没有负环，原不等式就有解，且解就为 dis，必要性成立
思考一下变量关系，若是关系无环比如说是一条链，容易想到，此时的不等式和最短路都是有解的。若是变量关系成环，设存在一个有向环 ，对应的边权依次为 ，，，。
由每条边对应的约束，有 将上述不等式逐项代入相消可得 若不等式组有解，则必有 否则会出现矛盾，而这也意味着图中不存在负环，所以此时最短路也是有解的，充分性成立
因此，不等式组有解等价于图中的最短路有解，这个转化是充分且必要的
...
今日一言 : Now or Never.
前言
换根 dp，用于解决根不固定的问题。所谓换根 dp，就是先求出一个根的答案，然后让子为根，将贡献由父转移到子，这样就能快速计算 n 个点分别为根时的答案
换根 dp 分为三步 :
先把树拎(ling)起来，找一点为根
计算每个子树的贡献
从根开始，由父节点向子节点传递贡献
洛谷 P3478
题意
找一个点，使其到所有节点的距离之和最大
解析
若选定一根，我们能 O(n) 求出距离之和，但每个节点都要算一次，那岂不是要 O(n2)
换根 dp 的思想可以轻松解决这个问题
先固定一个点为根，令 :
siz[u] 为子树的大小
ans[u] 为所有点到 u 的距离之和
我们可以先计算出根节点的答案，然后换根，若 u → v 进行转移，则转移方程为：
每次转移的时间复杂度 O(1)，从根开始，向子转移，O(n) 即可计算出所有点为根时的 ans，最后求 max 即可
MYCODE
1234567891011121314151617181920212223242526272829303132333435363738394041424 ...
前言
建站之后，很难没有统计网站访问人数的想法，本篇在 hexo 框架 + anzhiyu 主题环境下，利用 umami 0 成本实现网站流量统计，并实现统计模块。顺便说一下模块开发历程吧 (真是一波三折啊)
umami 统计工具感觉很 nice 啊，首先是 0 成本，然后你还能直接用它的 Umami Cloud 而不用部署自己的数据库，展示的数据也很全面，网页的 GUI 看着也是蛮舒服的
GUI 参考
写 umami 模块的过程也是挺坎坷的，遇到了很多坑。
准备工作
为了使用 umami，要先得到三样东西，website id，tracking code 和 api key，简单带过
首先在 umami 官网 注册账号，之后到控制台新增网站，然后打开右侧设置页面
可以看到 Website ID 和 Tracking code
为了统计网站数据，我们需要将 <script> 代码片段插入到网页的 <head> 里面，当有人访问网站时，该脚本会自动向 umami 发送数据以进行统计。在 anzhiyu 主题，主题的 _config.yml 文件中内置了插入接 ...
可持久化线段树是动态开点的权值线段树，同时维护了历史信息
对于一个普通的权值线段树，当我们让 cntv + + 时，影响的节点个数是 logn，可持久化线段树的插入操作就是基于此。也就是，当我们插入新值时只需要动态的新建 logn 个节点即可，其他节点都可以复用上个版本。这样我们就可以在较小的时空复杂度维护所有的历史记录，然后利用前缀和的思想维护区间信息。
简单应用区间第 k 大
我们将 ai 依次插入，用 cnt 维护某值域值的个数。若要查 [l, r] 的第 k 大，因为维护了插入了 a[1, l − 1] 和 a[1, r] 时的所有的 cnt 信息，就可以利用前缀和思想算出，只插入 a[l, r] 的 cnt 信息。
具体来说，若有节点 p，其对应值域 [x, y]，在插入 a[1, l − 1] 后值的数量为 cntu，在插入 a[1, r] 后为 cntv，则 cntv − cntu 就是 i ∈ [l, r], ai ∈ [x, y] 的值的个数。
这就相当于对于一个区间 [l, r]，知道了每个值域段的 cnt 信息，之后就可以类似于二叉搜索树去找第 k 大。
题目链接 ...
前言：
FWT, FMT 金牌知识点, 现在没必要学来着, 但题看都看了, 就顺便学了吧, 反正是个板子类的东西
( 目前大概都是当板子用了, 只能写写应用, 具体原理是一点不懂得, 我太蒟蒻l )
知识点
FFT - 快速傅里叶变换
多项式 F(x) = a0 + a1x1 + a2x2⋯，
令 fi 为 i 次项系数, 也就是 ai
多项式乘法：
说白了 fft 就是优化普通卷积, 也就是优化多项式乘法的工具
时间复杂度 O(nm) → O(nlog)
luogu - FFT 模板
MYCODE
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151 ...
