No21

周赛41-3-树的DFS

这个题目很经典，通过vector存储树，然后通过dfs对每一个结点进行标号。
一个数组负责通过给出下标得到结点，一个数组负责给出结点标号得到下标。
这两个数组通过dfs得到。

No22

周赛6-3-构造完全图

这道题很好啊，我个人比较喜欢。

思路

涉及两个思维跳跃。

1. 最大团任意开始扩展就行，不用一开始找最大的。
2. 最大团会一点一点往外扩增的。

状压代码就比较清晰了。

No23

周赛8-3 更新线路

思路

1. 反向存图
2. 记录前驱个数

No24

周赛16-3 子序列

这道题目做法比较经典，有借鉴意义，背一背吧。

记录第i个数左边的最大/小值，以及它右边的最大/最小值 ， 操作的时候不直接存储值本身 ， 而是存其下标，比较方便。具体通过正向枚举和反向枚举来实现~

No25

周赛43-3 合适数对

当时没做出来，哭死。当时忽略了人家元素可能是负的，以为数列的前缀和有单调性，写了个二分，快写完的时候才发现不对头。
困难的思路在于把这个数列问题转化成树状数组。

$sum_{r} - t < sum_{l-1}$ 当我们枚举$r$的时候，问题在于怎么可以迅速得到有多少个符合条件的$l-1$

思路

把前缀和的每一个元素以及他们和t的差值都离散化到vector里面去。
基于离散化之后的数轴，在其上建立树状数组。

我们从1到n枚举右端点，针对每一个右端点，查看有多少个已经出现的l符合条件$res+= i - query(get(s[i] - t))$，然后把这个前缀和的离散值标记到树状数组的数轴上。