树上倍增比起树链剖分代码短，容易查错，时空优，但是广度不如树链剖分. 具体实现 首先开一个n×logn的数组，比如fa[n][logn],其中fa[i][j]表示i节点的第2^j个父亲是谁。 那么就有： fa[i][j]=fa[fa[i][j-1]][j-1] 用文字叙述为：i的第2^j 个父亲 是i的第2^(j-1) 个父亲的第2^(j-1)个父亲。 下面是求i的第k个父亲的代码段： int father(int i,int k) { for(int x=0;x<=int(log2(k));x++) if((1<<x)&k) ...

对点权 例题： 题意描述：给定一棵树和节点上的值，然后执行下面操作： I u,v,value：把u和v路径上的节点的值都加上value； D u,v,value:把u和v路径上的节点的值都减去value； Q u:询问节点u上的值。 #include<cstdio> #include<vector> #include<cstring> #include<algorithm> const int maxn=50000+10; using namespace std; int n,m,q; int val[maxn]; int siz[maxn],...

题意：好几棵树，询问祖先为点i往上的第k个，且深度与点i相同点有多少个 解法：找点i的祖先很好找，如果这时我们搜索暴力，肯定会超时，所以就想到了二分优化，先预处理dfs序，得出新的编号，并开一个vector分别按深度记录下来，然后在查询祖先为t深度为h的点的个数时，只需要在vector第h层里二分，统计L[t]到R[t]之间有多少个点，要除去i点本身，所以减一就是结果. #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int maxn=1e5+...

主要用来求字符串的回文子串 时间复杂度是o（n） 思路是求以i为对称点，最长的回文子串，一开始先在字符串每个字符中间加个字符，使所有回文串成为奇回文串，然后不断推进的结果即可 例题为洛谷模板题，求最长回文子串的长度. #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=1e8+10; char str1[maxn<<1],str2[maxn<<1]; int p[maxn]; int manachar()...

AC自动机能解决单个母串，多个子串的问题，例如某一个子串出现了多少次，一共出现了几个子串等等. 网上常常说AC自动机是Kmp+字典树 简单来说为三步 1.建立子串的字典树 2建立fail指针，从而添加失败路径 3.跑母串 看一下例题 洛谷AC自动机加强版 题目描述 有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。 #include<cstdio> #include<algorithm> #include<cstring> #include<queue> usi...

因为之前学过树上倍增，还是挺好理解的，不能处理动态的 #include<cstdio> #include<cstring> #include<algorithm> #define M 25 #define N 100005 using namespace std; int n,m; int a[N],Log[N]; int f[N][M]; void GetLog() { int i; Log[1]=0; for(i=2;i<=n+1;++i) Log[i]=Log[i/2]+1; } void RMQ() { int ...

先说分块 牛 分块就是将一个序列，分成若干个区间（一般一个区间取sqrt(n)） 于是在进行选择分块策略时,主要解决以下几个问题: 1.针对不完整块如何进行处理? 2.完整的块如何进行处理? 3.需要对每个块维护哪些信息?如何进行预处理? 4.如何合并答案? 例子：给出一个长为 n的数列，以及n 个操作，操作涉及区间加法，单点查值。 有一个数据记整块的加值，如果是整个区间，直接改加值，不完整的区间单独改每一个数的值. 接下来说莫队 牛 例：一个区间多次询问，问一个区间内有多少种数，暴力的解法就是，一个左指针，一个右指针，询问一个一个查，左边不行就推左边，右边不行就推用边，直到和询问区间重...

题目： 定义一张无向图 G=⟨V,E⟩ 是 k 可染色的当且仅当存在函数 f:V↦{1,2,⋯,k} 满足对于 G 中的任何一条边 (u,v)，都有 f(u)≠f(v)。 定义函数 g(n,k) 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说，g(3,1)=0,g(3,2)=2,g(3,3)=3。 现在给出三个整数 n,l,r，你需要求解： 在l到r区间内g(n,i)的和 mod 998244353 输入 5 3 1 1 3 2 2 5 2 4 10 3 9 1000 123 789 输出 0 2 23 280 332539617 思路，易知当颜色...

题意：一个长度为n的数列，和一个长度为m的数列，每项相乘的出来的所有结果中第k大的值，其中数列长度为1e5,整数大小1e6 思路：先二分要求的值，再定住每一个矩阵n，去二分另一个矩阵m，得出大于等于这个值的个数，直到找到这个k即可。 时间复杂度（O（nlogn^2）） #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue>...

在一棵有根树 T 上，任何两点间的最短路径都能够分为两个阶段： 从起点出发，沿着向根的方向走若干条边。 向着终点，沿着离开根的方向走若干条边。 定义一条路径的权值为向上走的边数乘上向下走的边数。特殊地，当起点等于终点的时候，两阶段的边数都是 0；当起点是终点的祖先的时候，第一阶段的边数是 0；当终点是起点的祖先的时候，第二阶段的边数是 0------这三种情况下，路径的权值都是 0。 现在给出一棵 n 个节点的无根树 T 和 m 条路径 (a​i​​ ,bi​​ )。对于每一个 r∈[1,n]，你需要计算当 r 是根节点的时候，所有路径的权值和是多少。 输入格式： 第一行输入两个整数...

题目：一棵树有n个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和。 树上启发式合并真神奇，时间复杂度只有O（nlogn） 看下思路 第一步：我先像树剖那样，跑出重儿子。 第二步：我们dfs这个树，比如说，我们现在跑到了u节点。首先优先跑所有轻儿子，采用尾递归的方式，统计轻儿子的答案。期间维护一个通数组cnt，存的是以当前轻儿子为根的子树的颜色数量。跑完后将答案赋予这个轻儿子节点，然后清空cnt数组，开始跑下一个轻儿子。 第三步：轻儿子跑完后，我们开始跑重儿子。跑完后，注意：我们不在清空cnt数组，然后逐个再跑一遍各个轻儿子。将结果累计到cnt里面，这里就...

分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像单个相关系统把计算机整合起来提高效率只有单个节点无法满足日益增长的计算，储存任务，且硬件的提升得不偿失，且应用程序无法进一步优化，我们才需要考虑分布式系统将一系列功能分开，放在不同的电脑上，功能麻烦就多分配 项目架构单一应用架构当网站流量很小时，只需一个应用，将所有功能都部署在一起，以减少部署节点和成本。此时，用于简化增删改查工作量的 数据访问框架(ORM) 是关键。垂直应用架构当访问量逐渐增大，单一应用增加机器带来的加速度越来越小，将应用拆成互不相干的几个应用，以提升效率。此时，用于加速前端页面开发的 Web框架(MVC) 是关键。...

先说说b树B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;插入时如果关键字数目超过了阶数，就将当前块分成两块，前面的用之前那块，后面的用新建的块，并将中间的关键字放到父亲节点中去，然后加入新的块的指针 再看b+树B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询...

先看下什么是红黑树红黑树的性质性质1：每个节点要么是黑色，要么是红色。性质2：根节点是黑色。性质3：每个叶子节点（NIL）是黑色。性质4：每个红色结点的两个子结点一定都是黑色。性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。红黑树节点的插入我们可以发现在插入节点的父节点为红节点时，除去染色，旋转过程和二叉平衡树是一样的，不过由于二叉平衡树严格要求两个子节点的高度差不能超过1，所以在插入时会频繁破坏规则旋转，而在红黑树中，由于黑节点较多（大概是2倍），经常出现红节点直接插到黑节点上就完事的情况所以效率较高，不过，如果你要说，单单在查找方面的效率的话，平衡树比红黑树快。所以，我们也可...