-
根号分治
===Index 模板 区间加查询区间最小值 区间小于等于x的数量模板需要针对具体题目修改的部分 S: 待分块数据类型，一般是读入数据类型，按需选择int, long long, mint等。 T: 查询的答案数据类型 UNIT: 每个块的结果的单位元 op(x, y): 不同块的结果怎么合并，按需选择 sum, min, max等。 get_part(l, r): 零碎的块的结果统计，一般暴力遍历即可 get_all(l, r): 完整块的结果统计 update_pa...…
-
可持久化数据结构
===Index 可持久化线段树 静态区间第k小 矩阵操作 矩阵和 带修改区间中k出现数量 树上路径权值第k小 可持久化懒标记线段树 可持久化数组 维护可持久化数组 可持久化线段树模板#if __cplusplus >= 201703L#define CHK(t) if constexpr (t)#else#define CHK(t) if (t)#endiftemplate &l...…
-
卷积
===Index gcd_lcm卷积模板 gcd卷积 gcd pair之和 统计gcd数对 lcm卷积gcd_lcm卷积模板template <class T> void multiple_zeta(vector<T> &f) { int N = int(f.size()) - 1; vector<char> is_prime(N + 1, 1); for (int p = 2; p <= N; p++) if ...…
-
数位dp
===Index 力扣周赛题目 相邻数位差的绝对值恰好为1的数 整除k且奇偶数位数目相同的数 数字1出现的个数 旋转数字数目 至少有1位重复的数字 二进制表示不含连续1的数字 数位和在某个区间内的数字 其它题目 无相邻重复数字的数 不降数 windy数-相邻数字之差的绝对值至少为2 每个数字的出现次数 平衡数字 被数位和整除的数字...…
-
矩阵运算
===Index 矩阵模板 字符串转换 类斐波那契数列矩阵模板template <typename T>struct Mat { vector<vector<T>> dat; Mat() = default; Mat(int n) : Mat(n, n) {} Mat(int n, int m, T fill_value = T(0)) : dat(n, vector<T>(m, fill_value)) {} ...…
-
树上启发式合并&欧拉序
===Index 启发式合并 子树出现次数最多的颜色编号之和 树上数颜色 欧拉序 查询路径和 路径上等于k的节点数 路径上被k整除的节点数 bfs序 权值大于p的节点最小高度 树上启发式合并用于解决树上对所有子树的查询问题，一般不带修改，总时间复杂度为 O(nlog(n))启发式合并模板struct DsuOnTree { int n, lst_rt; v...…
-
倍增算法
===Index 模板 跳k次后的位置 k步后的距离之和与最小值 k次传球后最大函数值 城市之间最少边数 两点之间的最少天数 树上倍增 模板template <class S, S (*op)(S, S)> class BiLiftring { int n = 0; vector<vector<int>> _nexts; vector<vector<S>> _prods...…
-
后缀数组
===Index 模板 判断子串 统计子串 不同子串数目 s和t的最长公共子串 子串排序 所有子串borders总和 最大循环子串 从字符串首尾取字符最小化字典序 m个数组的最长公共子数组模板后缀数组主要关系两个数组： sa和rk，sa[i]表示表示将所有后缀排序后第i小的后缀的编号.rk[i]表示后缀i的排名,这两个数组满足性质:sa[rk[i]] = rk[sa[i]] = itemplate<typename T>struct ST { int ...…
-
图论选题
===Index 被最多点到达的节点集合 最小树形图模板 虚根最小树形图 支配树 曼哈顿生成树被最多点到达的节点集合hdu3639n个点，m条有向边的图，定义节点u的得分为所有不等于u且能通过某条路径到达节点u的节点数目，求节点的最大得分，以及拥有最大得分的节点集合。 2 <= n <= 5000 1 <= m <= 30000分析首先进行强联通分量缩点，缩点后建反向图，在该拓扑图上求每个节点能到达的节点数目即可。void solve() { i...…
-
geeksforgeeks选题
===Index 区间内匹配括号对数量 好数组需要的最少删除元素数量 s到t波浪路径最短路 使字符串相等的最少预处理操作次数 从s到t经过中间节点的最短路径 连通图中的k个节点 重排字符串 乘积数组第k大数 q次操作后可能的字符串数量 循环字符串插入区间内匹配括号对数量geeks link输入括号字符串s(长度n)，和m个区间询问，每个询问给定区间[l,r]，返回长度为m的数组ans，ans[i]表示第i个询问的区间内平衡括号对数。 1 <= n, m <...…
-
换根dp模板
===Index 模板 简介 不带边权例题 EDPC-V Subtree Maximum White Subtree 去掉一个端点的最长路径和 树中距离之和 可以到达每一个节点的最少边翻转次数 统计可能的树根数目 树异或 边权例题 树上边权加终点点权最长路径 最小神秘值 模板template <class T, // ...…
-
模板及例题
===Index algorithm #并行二分 datastructure 最小绝对值和 前k大元素和 离线矩形加矩形求和 带修改子数组不同元素数量和 区间与等差数列和 string runenumerate algorithm并行二分第k大数给定n个初始为空的数组t1,…tn, 首先执行m次元素插入操作。每次操作给定 l, r, v，在 t[l..r] ...…
-
积性函数
===Index 积性函数简介 狄利克雷卷积 例题 lcm求和 gcd求和 积性函数简介考虑一个定义域为正整数的函数f，对于任意两个互质的正整数a,b, 均满足 f(a,b)=f(a)*f(b), 则函数f被称为积性函数。如果对于任意两个正整数a,b，都有 f(ab)=f(a)*f(b) ，函数f也被称为完全积性函数性质 对于任意积性函数 f(1)=1 欧拉函数为积性函数，当n>1时，1..n中与n互质的整数和为 n*ph(n)/2 ...…
-
生成函数
===Index 普通生成函数 购买水果方案数 获得分数的方法数 满足质因数分解的方案数 指数生成函数 排列组合 常见生成函数 普通生成函数对于一个序列 a = a[0], a[1],...,a[n-1], a的普通生成函数为F(x) = a[0] + a[1] * x + a[2]*x^2 + ... + a[n-1] * x^na可以是又穷序列或无穷序列。例如序列 [1,2,3] 的生成函数为 ...…
-
树哈希
===Index 简介 模板 对称树简介树哈希将一颗树结构转成哈希值储存起来，以降低复杂度，在判断一些树是否同构等问题场景中广泛使用。哈希方法我们计算以u为根节点的子树G的哈希值 如果u是单独的叶节点, 定义 p(u) = 1, 否则，设d为树的高度，设u有k个直接相连的子节点，其哈希值分别为p1,p2…pk 则子树G的哈希值 P(G)=(x+p1)*(x+p2)*...*(x+pk),其中x为哈希的base，一般为一个随机的质数。模板// 3哈希容易tle，默认双哈希, u1...…
-
树分治
===Index 简介 最近的红色节点简介树分治可以用来解决如下问题: 在一棵树上有多少条路径的长度正好是k 在一棵树上有多少条路径的xor和为k，或者所有xor路径的总和。 更新一个节点从黑到白或从白到黑，查询一个节点到白节点的最短路径通过对原树进行重心分解，得到一颗新树,该树满足如下性质 新树包含原树的所有节点，原树中的每个节点都是一些子树的重心。 新树的高度最多 log(N) 原树中任意两点 x,y 的路径，在新树中都被分成 (x, z) 和 (z, y)两段，其中z...…
-
强连通分量
===Index 有向图强连通分量 scc模板 有向图中能被所有节点到达的节点数目 有向图变为强连通图需要添加的边数 无向图的双连通分量 边双连通分量eDCC 无向连通图最少加几条边能变为一个边双连通分量 点双连通分量vDCC 有向图强连通分量强连通：若一张有向图的节点两两互相可达，则称这张图是强连通的。强连通分量(SCC)：极大的强连通子图scc模板使用数组 时间戳 dfn[x]: 节...…
-
树链剖分
===Index 基础概念 模板 使用说明 例题 树链剖分 路径颜色翻转 边权转点权 边权转点权2 加点删点求深度 路径上最大最小子数组和 基础概念基础概念 重儿子：父节点所有儿子中，子树节点数目最多的节点 重边：父节点和重儿子练成的边 重链：由多条重边连接而成的路径结论 整棵树会被剖分成若干条重链 轻儿子一定是某条重链的顶点 任意一条路径被切分成不超过log(n)...…
-
莫队算法
===Index 普通莫队 简介与模版 区间中有多少个不同的数 区间中有多少个逆序对 树上莫队 树上统计2 路径查询 树上逆序对 简介与模版莫队，是一种解决区间查询等问题的离线算法，基于分块思想，复杂度为 O(n·sqrt(n)) 。一般来说，如果可以在 O(1) 内从 [l,r] 的答案转移到 [l-1,r], [l+1,r], [l,r-1], [l,r+1] 这四个与之紧邻的区间的...…
-
快速沃尔什变换
===Index 简介与模板 或运算 与运算 异或运算 同或运算 异或例题 统计异或值在范围内的数对有多少 频率最高的子序列异或和 所有子数组异或和之和 按位与例题 所有子数组按位与和之和 按位与奇数个1异或偶数个1的子数组数目 按位或例题 所有子数组按位或和之和 按位或最大的最小子数组长度 按位...…
