day2 线段树, 树状数组

day 1 倍增 RMQ ST表 LCA

T1

题目描述

阿米巴和小强是好朋友。
阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮，他兴奋地叫个不停。而阿米巴则很淡定，他回想起曾经的那些日子，事业的起伏，情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来，简直什么都不算。
于是，这对好朋友不可避免地产生了分歧。为了论证自己的观点，小强建立了一个模型。他海面抽象成一个$1$到$N$的排列$P[1…N]$。定义波动强度等于相邻两项的差的绝对值的和，即：
$L = | P_2 - P_1 | + | P_3 - P_2 | + \cdots + | P_N - P_{N-1} |$
给你一个$N$和$M$，问：随机一个$1…N$的排列，它的波动强度不小于$M$的概率有多大？

答案请保留小数点后$K$位输出，四舍五入。

差分约束用于解决如下的一些约束的可行解：

分块思想，常用于处理区间问题，大概是把区间分为若干个块分别维护。

T1

https://www.luogu.com.cn/problem/P6850
纯模拟没啥可说.

T2

https://www.luogu.com.cn/problem/P6851

部分分：

1. c = 0
   胜负无关，那么可以直接做，每次取最大就行了

正解：

使用贪心，每次不能赢就放弃机会，能就选最省的。

T3

1. n, m <= 20
   使用暴力+奇怪数据结构可过.
2. val = 0
   区间差分排除法。
3. 正解
   合并区间，可以用线段树来标记。
   [l,r,val]相当于 l - r 里面有 0-val-1 却没有 val
   如此就可以很快合并。
   做完之后，就随便填就 ok 啦

T4

构造题。

1. 矩阵构造：
   
2. 面条构造
   
3. 三角构造
   画很多三角再连接就好了
4. 正解
   把路径看成点，车站看成边

0x01 前置芝士🎂

0x02

1. 
2. 出现这个页面，搜索你想交的题
3. 
4. 
5. 
6. 点击 $Submit$ 提交
7. 

Linux 文件？设备？

数学恶补
$\in $ 是属于，$G$ 是图，$V$ 是点，$E$ 是边

1. 基本概念

1.1 流网络，不考虑反向边

流网络 $G=(V,E)$ 是一个有向图，图中每一条边 $(u,v) \in E$ 有一个非负的容量值 $ c(u,v) \ge 0 $
且，若集合 $E$ 包含一条边 $(u,v)$ ，则不包含 $(v,u)$.

$(v,u) \in E \Rightarrow (u,v) \notin E$

1.2 可行流，不考虑反向边

1.2.1 两个条件：容量限制、流量守恒

1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量

1.2.3 最大流是指最大可行流

1.3 残留网络，考虑反向边，残留网络的可行流f’ + 原图的可行流f = 原题的另一个可行流

1.4 增广路径

1.5 割

1.5.1 割的定义

1.5.2 割的容量，不考虑反向边，“最小割”是指容量最小的割。

1.5.3 割的流量，考虑反向边，f(S, T) <= c(S, T)

1.5.4 对于任意可行流f，任意割[S, T]，|f| = f(S, T)

1.5.5 对于任意可行流f，任意割[S, T]，|f| <= c(S, T)

1.5.6 最大流最小割定理

1. 可行流f是最大流
2. 可行流f的残留网络中不存在增广路
3. 存在某个割(最小割)[S, T]，|f| = c(S, T)

1.6. 算法

1.6.1 EK O(nm^2)

1.6.2 Dinic O(n^2m)

1.7 应用

1.7.1 二分图

1. 二分图匹配
2. 二分图多重匹配

1.7.2 上下界网络流

1. 无源汇上下界可行流
2. 有源汇上下界最大流
3. 有源汇上下界最小流

1.7.3 多源汇最大流