Peterliang

模板

PAT挑战日记(15) 《算法竞赛进阶指南》系列题解(4) 心路历程(1) 未归档(5) 题解(145)

/ 注册

全部文章 / 模板（共2篇）

树上求LCA两种方法

一、向上标记法比如求x，y的lca，我们先从x向上走到根节点，中途标记每个被走过的点，然后从y向上标记，直到遇到第一个被标记的点就是他们的lca了。(不适用于多次查询操作）时间复杂度：O(n) 二、树上倍增法这种方法主要是利用了倍增的思想，不断地向上试探，同时利用dp不断转移到上面，然后即可求出...

LCA DP

2020-10-05

0 521

线段树的各类板子题模板（有待更新）

对于区间的单点处理： #include<iostream> using namespace std; const int N=1000010; typedef long long ll; ll a[N<<2],tree[N<<2];//首先对于数组我们要开正常数...

2020-07-18

0 731