## 2022/1/17

#### P1901 

单调栈从前往后，从后往前跑两遍，统计接收的能量值，再找最大值即可。

#### P1484

将每一个点与左右连好边，再放入大根堆中，从堆顶逐个取出，再将其左右连接的点的置加一起再减去原先堆顶的值，左右连的边与原先堆顶的一样，放入堆，再将其左右连接的点删除，若堆顶为负则不取，输出所有从堆顶取出的和即可。

## 2022/1/18

#### P5937

用 `map ` 标记一个 `vector` 内存所有以同一个 $l$ 开始的被询问的区间，每读入一个看其区间中收尾相连的区间的奇数区间的个数，判断其奇偶性是否与原区间奇偶性一样，若不同，则其是不合法的。（这个做法是假的，只有 $70$ 分~~但我用一些玄学做法A了~~）

#### P3420

用并查集将每个钥匙的关系连一起，再看有几个祖先即可。

#### P2024

开一个并查集，再开一个数组存权(re)（$0$ 同种，$1$ 捕食，$2$ 被捕食）。

##### 合并：

若:

A<-a-B

B<-b-C

A<-c-D

则有：

$a=(c-b+3)\mod 3$（同类）

$a=(c-b+4)\mod 3$（捕食）

##### 查找（路径压缩）：

若:

A<-a-B

B<-b-C

设路径压缩后：

A<-c-C

则有：

$c=(a+b)\mod 3$

再按题意判断模拟即可。

## 2022/1/19

#### P3373

模板题，多一个标记算乘法即可。

#### P5459

可以来一个前缀和数组，我们则要求：

$i \leq j, L\leq sum[j]-sum[i]\leq R$

用归并求逆序对差不多的思想，离线分治用一个队列模拟即可。

#### P1295

设 $dp_i$ 为分到 $i$ 时的最小的每段的最大值。

则：

$$dp_i=\min\limits_{j=1}^{j\leq i} \left\{ {dp_{j-1}+\max\limits_{k=j}^{k\leq i}}h_k \right\} \left( \sum\limits_{i=1}^nh_i\leq m \right)$$

~~暴力求加个快读吸个氧就过了~~

## 2022/1/20

无（我果然还是太蒻了）

## 2022/1/21

#### SP3267

莫队跑一下，若删除操作后那个数没了则答案减 $1$ ,若加入操作后那个数之前则答案加 $1$ 即可。

## 2022/1/22

#### P2061

将房子高度从大到小排序，再逐个用ODT区间推平，统计答案即可。

####  简单题

模拟即可，（缺失的那个东西是lowbit）。

## 2022/1/23

#### P3379

模板题，可用倍增求LCA。

## 2022/1/24

#### P3128

对每个相连的点的差分数组加一，它们的LCA和LCA的父亲减一，最后遍历一遍求原数组，最后统计最大值即可。

#### P3258

同上题，只不过要差分数组加的是第一个节点和第二个节点的父亲，且遍历输出的是全部。

#### P6869

同上上题，只不过要将它们LCA减二，LCA的父的父亲不减，再最后遍历时多传一个是哪条边，对于每次统计哪种方案花的钱最小即可。