爱飞鱼的blog

经典数据结构问题 静态区间颜色数 1234567891011121314151617181920212223242526272829303132void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; int m; cin >> m; int mx = *max_element(alls(a)); vector<vector<pii>> q(n + 1); for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; q[r].push_back({l, i}); } deb("?"); ...

树上路径问题—树形dp [「REMAKE系列」树形dp篇 - Roshin - 博客园 (cnblogs.com)](https://www.cnblogs.com/Roshin/p/remake_tree_dp.html#:~:text=树上路径1 link) dls的树形dp - 牛佳文 - 博客园 (cnblogs.com) Codeforces 633 F The Chocolate Spree(树形dp，两条不相交链节点权值和最大)_树上求不相交的两条权值最大路径-CSDN博客 SPOJ Two Paths 树上不相交路径乘积最大值_树上最多路径 边不相交路径-CSDN博客 [P9047 [PA2021] Poborcy podatkowi - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P9047#:~:text=给定一棵 nnn 个) 树上路径问题常见手法：树上动态规划（路径问题） - 算法小站...

虚树 模板： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149struct edge { int v, w;};struct HLD { int n; vector<int> siz, top, parent, l, r, hson, dep; ...

长链剖分 https://blunt-axe.github.io/2019/11/25/20191125-Longest-Decomposition-Notes/ Problem - E - Codeforces [P3899 湖南集训] 更为厉害 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [P5904 POI2014] HOT-Hotels 加强版 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) https://www.cnblogs.com/maoyiting/p/14178833.html#/cnblog/works/article/14178833 重链剖分定义子树大小最大的为重子节点，而长链剖分定义子节点中子树 深度最大 的子节点为重子节点。如果有多个子树深度最大的子节点，取其一。如果没有子节点，就无重子节点。 性质：链的长度定义为链包含的点数 任意节点 p 的 k 级祖先q所在的链的长度一定大于 k 证明：分情况讨论。根据定义q→p 链的长度为 k+1 ，如果 p 和 q 在同一条链上，那这条链的长度自然大于 k...

后缀自动机SAM 板子： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899struct SAM { static constexpr int asz = 26; struct Node { int len; int fail; int cnt = 0; array<int, asz> next; Node() : len{}, fail{}, next{} {} }; vector<Node> t; int tot = 0;...

回文自动机PAM 在线数据结构「笔记」回文自动机 - Luckyblock - 博客园 (cnblogs.com) 每个状态仅代表唯一的本质不同的回文子串字符串 。s 的本质不同回文子串的数量至多只有 |s|个，则 PAM 的状态数个数是 O(n)级别的 算法原理就是增量法构建...

CCPC2023秦皇岛 C.题意：给定一个字符串，多次区间询问给定一个子串。问有多少种方案删掉最短的区间使得子串变成回文串 Sol：考虑每次询问可以独立处理，当然并不是指把子串单独提出来，而是按顺序正常回答。 一个关键的点是，考虑如果第一个字符和最后一个字符不一样，那一定要删一个，依次推理下去，我们可以得到应该保留最长回文前缀或最长回文后缀。 再考虑如果第一个字符和最后一个字符一样，那我们类双指针缩小删除区间，直到两边不一样。此时又回归到第一种情况。 根据上面这个观察，我们得到获得最小删除代价的做法： 对于一个区间[l, r] 我们首先可以先让首尾相同字符不断相 消, 最后剩余区间[x, y], 如果这个区间为空则为回文串。这一部分等价于求原串后缀l 和反串后缀n − r + 1 的最长公共前缀( LCP ), 再对区间长度取min。 如果不为回文串, 那么str[x]=str[y]str[x] = str[y]str[x]=str[y], x, y 其中之一会被删除。 删除最少长度, 等价于保留最多长度, 即保留x 开头的一个 回文串或y...

行列式与矩阵树定理 行列式取模板子：对于模数非质数采用辗转相除 消元操作是Θ(n3)Θ(n^3)Θ(n3)的，辗转相除法是 Θ(log⁡p)\Theta(\log p)Θ(logp) 的，因为辗转相除和消元每次必然使得数变小，势能只会减少，所以这个是均摊到Θ(n2)Θ(n^2)Θ(n2) 的，最终有复杂度 Θ(n2log⁡n+n3)\Theta(n^2\log n+n^3)Θ(n2logn+n3)。 P7112 【模板】行列式求值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 12345678910111213141516171819202122232425262728293031323334ll MOD;int cal(vector<vector<int>>& a, int n) { ll flag = 1; // 转化成上三角矩阵 for (int i = 1; i <= n; ++i) { // 枚举行 for (int k = i + 1; k <=...

编译命令 1234bison -d parser.y -o parser.tab.c> flex -o lexer.c lexer.lgcc -o parser lexer.c parser.tab.c ast.c main.c dot –Tpdf ast2.dot –o graph2.pdf

转载自 https://blog.csdn.net/qq_37978559/article/details/109782755?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169173063816800197041324%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169173063816800197041324&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2