引入在处理区间问题时，我们常常用分治思想，将区间分为若干小区间，然后对小区间进行区间统计，最后进行区间合并，但是当区间信息不方便合并时，我们可以使用莫队。详解例如对于小B的询问。题意：小B有一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$，求： $\sum\limits_{i=1}^k c_i^2$。其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。小B请你帮助他回答询问。分析对于这道题，我们发现它有几个性质：1.不方便进行区间信息合并数据范围较小，但可以卡掉 $O(n^2)$根据一个已知答案的区间 $[l, r]$，可以快速求出区间 $[l, r + 1]$ 的答案。对于性质1，我们无法用线段树，前缀，st表等结构来维护，例如线段树的统计信息无法维护。对于性质3，具体这样实现的。比如我们增加一个元素 $v$ 进来，相当于让答案从 $c_v^2+...$ 变成了$(c_v+1)^2+...$，那么相当于答案增加 $2 \times c_v+1$，减少元素也类似。于是我们得到一个暴力算法，我们
定义给一个有向图 $G=(V,E)$。对于边 $(u,v)$ 有容量 $w(u,v)$。可以理解为为水管在单位时间可以流过的最大水量。现在给定源点 $s$，和汇点 $t$，可以将源点理解为单位时间内可以留任意的水量的水龙头，汇点可以理解为可以装无限水的容器，最大流指源点发出的“水”经过“水管”单位时间可以流到汇点的最大水量。FF思想对于求网络最大流问题，我们有一个基础的想法：从源点dfs，如果dfs到了汇点就将这条路径上“流水”，而流的水量就是当前我们dfs到的源点到汇点的路径中边容量的最小值，然后将所有dfs到的边都流去这个水量，相当于将这些边的容量都减少这个水量，在之后的dfs中不走已经满了（没有容量）的边。但是我们需要改进这个算法，我们发现dfs的一条路径显然不一定是最优的，所以我们让这个算法可以后悔。如何后悔，我们对于每一条边建一条容量为0反向边，每当一条边溜了 $x$ 的流量时就将反向边的容量扩大 $x$ 也就是给自己 $x$ 的反悔空间，那么现在我们就可以写出一个基础代码了，这个基础代码就是FF算法。tip:对于求一条边的反向边我们可以利用链式前向星存图方式的边的编号，让编
前言我们知道线段树可以处理区间修改/查询操作，那么如果这个区间修改/查询变成了树上任意一条路径上点的修改/查询呢？比如我们需要满足一下几个操作 ：给 $u$ 到 $v$ 路径上的每一点都加上 $k$查询 $u$ 到 $v$ 路径上每一点的和。如果数据大的话，暴力算法是不能胜任的。树剖我们考虑将树上问题转化为区间问题，然后用线段树处理。但是一条 $u$ 到 $v$ 路径上每一点在线段树的位置不一定是连续的，所以我们可能要进行多次区间操作，因此最坏情况下甚至不如朴素算法。所以我们尽量让多的点的编号连续。概念现在我们引入几个概念和定义：时间戳 $dfn_x$：dfs时到达这个点的时间成为这个点的时间戳；重儿子 $son_x$：所有儿子中子树最大的儿子；重边：由 $x$ 到 $x$ 的重儿子的一条边；轻边：由 $x$ 到 $x$ 的非重儿子的边；重链：若干条连续的重边合称为连续的重链；$top_x$：$x$ 所在重链的顶端（当 $x$ 不在重链上时可以理解为自己到自己的重链 $top_x=x$）；f_x：$x$ 的父亲；dep_x：$x$ 的深度。核心思想对于以上的东西，我们可以通过两编 $d
1.概念强连通分量：在有向图或无向图中的点集，保证集合中每两个点都可以互相到达。割点：一个点是割点当且仅当删除这个点之后连通块的数量会增加。桥：一条边是桥当且仅当删除这条边后连同快的个数会增加。树边：遍历一个图时的dfs树上的边。非树边：图中除了树边以外的其他边。dfn：时间戳，即dfs一个图时点是第几个被遍历到的。low：子树内所有节点所能通过走非树边到的点的dfn的最小值。2.算法tarjan的算法本质其实就是在dfs图的时候求dfn和low这两个值，通过这两个值可以求出很多东西，详见应用。对于dfn很好处理，在dfs时直接记录即可。对于 $low_x$，以及现在有一条 $(x,y)$ 的边，如果 $y$ 还没有遍历过，说明这是树边，$y$ 是 $x$ 子树内的节点，所以 $low_x=\min\{low_x,low_y\}$。如果 $y$ 已经遍历过了，则这条边为非树边（此时 $y$ 有可能为 $x$ 的父亲，因为可能有重边）或者树边（此时 $y$ 必定 $x$ 的父亲）。如果是非树边的话 $low_x=\min\{low_x,dfn_y\}$。3.应用3-1割点如果一个点是割点
ybaggio
