差分约束系统
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
123456789101112131415161718192021222324252 ...
前言
建站之后，很难没有统计网站访问人数的想法，本篇在 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 主题，主题 ...
可持久化线段树是动态开点的权值线段树，同时维护了历史信息
对于一个普通的权值线段树，当我们让 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
信息，之后就可以类似于 ...
基于 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 ...
前言：
FWT, FMT 金牌知识点, 现在没必要学来着, 但题看都看了, 就顺便学了吧,
反正是个板子类的东西
( 目前大概都是当板子用了, 只能写写应用, 具体原理是一点不懂得,
我太蒟蒻l )
知识点
FFT - 快速傅里叶变换
多项式 F(x) = a0 + a1x1 + a2x2⋯，
令 fi
为 i 次项系数, 也就是 ai
多项式乘法：
说白了 fft 就是优化普通卷积, 也就是优化多项式乘法的工具
时间复杂度 O(nm) → O(nlog)
luogu - FFT
模板
MYCODE
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810 ...
B.Blocks
题意:
平面上有 n 个方块,
给出左上右下角坐标, (x1, y1), (x2, y2)
不断重复以下操作
随机选任意一个 (可能重复选同一个)
将该方块涂黑
一直操作直到 [0, 0] × [W, H]
的区域被完全涂黑
求操作期望次数
(n ≤ 10, x, y, W, H ≤ 1e9)
解析:
n 很小, 容易想到状压 dp
定义 dpS →
从状态 S 到完全染黑的期望次数，S 中的 1 代表该矩形选过
期望 dp 方程化简
若染色已经完成, 则期望步数为 0, dpS = 0
选到已选过的矩形, 概率 , 形成环,
移项即可解决
令 S 为当前的状态, x 为
S 中 1 的个数
判断已经全部染黑
提供两种方法
1. 二维离散+二维差分:
不难发现大部分区域都是无用的, 对 x, y 轴分别离散即可
离散后大概只有 21 行/列
现在想要 [x1, y1] × [x2, y2]
的矩形区域 +1
离散后范围较小, 可以直接暴力对矩形区域 +1
之后暴力 ...
XCPC
未读HDU
25春季联赛 - 0 - 1007
题意:
给定长度 n 的数组 a,
定义 [l, r] 价值为
⨁i = lrai ⋅ (r − l + 1),
定义 f(a) 为数组
a 划分后的最大价值和,
求
(n ≤ 2e5, 0 ≤ ai < 1024)
解析:
很容易想到 n2
dp
pre
为前缀异或数组
定义 dpi
→ 用前 i 个元素能得到的最大价值
转移方程:
复杂度不可接受, 尝试优化
我们拆开式子:
1.先考虑一个更简单的式子: 观察左侧部分: dpj − (prei ⊕ prej) ⋅ j
当我们在 j 时, 未知量只有
prei
定义 g(x) → max{dpj − (x ⊕ prej) ⋅ j}
我们遍历到 j 时, 对所有可能的
x 的值进行预处理
转移方程:
由 ai < 1024
可知 x < 1024
预处理时间复杂度 O(1024)
转移复杂度 O(1)
总时间复杂度 O(1024 ⋅ n)
2.让我们回到原式 类似地
定义 g( ...
XCPC
未读CF1887D
题意：
定义一个数组是好的，仅当其可分割成两个非空数组，使得左边元素都小于右边元素
即满足 max(al…ak) ≤ min(ak + 1…ar)
给定排列，q次查询，问 [l, r] 的子数组是否是好的
(n, q ≤ 3e5)
解析：
固定 l，r，若枚举 k，左右两侧都是单增，因此整体不存在单调性
法 1：
二维离线
从值考虑
我们考虑左侧区间中的最大值，
若 ai
成为最大值，我们记 i 左侧第一个大于 ai 的元素位置为
l1，则有限制 l1 < L ≤ i
我们记 i 右侧第一个大于 ai 的元素位置为
r1，记 r1 右侧第一个小于 ai 的元素位置为
r2，则有限制 r1 ≤ R < r2
这样的 [L, R] 就是左侧以 ai
为最大值的好区间
( i 左右找 > ai
的第一个位置是很典的问题，可以用单调队列，笛卡尔树，按值枚举甚至还可以用
set )
也就是，以 ai
为最大的合法情况落在矩阵 L ∈ [l1 + 1, i], R ∈ [r1, r2 − 1 ...
前置知识 - 状压 dp：
(220 ≈ 1e6，317 ≈ 1e8)
1. SOS DP - 子集和 dp：
每个集合有一个权值f(S)，我们想求集合 S 所有子集的权值和 dpS，即
(注意：每个子集有且仅有一次贡献)
若暴力求解，枚举S，然后枚举sub，时间复杂度 O(3n)
SOS dp：先枚举位，让所有集合逐位转移，时间复杂度 O(n ⋅ 2n)
[理解参考]
参考代码
123456789// f(S) 权值数组已知dp = f; // 赋初值for(int p=0; p<20; p++){ // 先枚举位 for(int S=1; S<=full; S++){ // 再枚举所有集合 if(S >> p & 1){ dp[S] += dp[S ^ (1 << p)]; } }}
2. 子集划分 dp
时间复杂度 O(3n)
大致操作是枚举 mask，然后枚举子集 S，和补集 T
然后 merge(S, T)
和区间 dp 一 ...
.jpg){kind=avatar}
