===== 霍尔定理 =====

设二分图的两部分为$X$、$Y$，且$|X|\leq|Y|$。

则定理描述为：二分图存在完美匹配，等价于对于$X$的任意子集$X^{'}$，与它们中任意点相连的$Y$的结点个数$\ge |X^{'}|$。

[[https://codeforces.com/gym/102268/problem/D|gym102268D Dates]]

**题意:**

给你一张二分图，左边有$t$个位置，右边右$n$个带权点，第$i$个点与$[l_i, r_i]$所有点连边，匹配的值为匹配中右边点的权值和，求最大权匹配。

其中，$1 \leq n, t \leq 3 \times 10^5, l_i \leq l_{i + 1}, r_i \leq r_{i + 1}$

**题解:**

将右边的点按照权值从大到小排序，依次加入查看有无完美匹配，有就选择否则跳过。按照我个人的理解，如果让一个权值更小的替换了当前某个已经选择的某个点，匹配数不会变多，答案也不会变优。

于是，问题转化成了如何判定是否存在完全匹配，这就用到了霍尔定理，考虑右边的点中被选择的那些，选择其一个子集，判断是否所有子集的邻域（即与其相邻的点构成的集合）大小都比子集本身大。

如果我们选择的子集对应的区间是不连续的，霍尔定理的条件成立等价于对于断点两边分别成立，所以只用考虑选取的子集对应的区间连续的情况。

又因为$l_i \leq l_{i + 1}, r_i \leq r_{i + 1}$，也就是说只需要考虑选择的子集的编号连续的情况，即

$\forall 1\le i< j\le n,[i,j]\text{中被选择的右侧点个数}\le [l_i,r_j]\text{中左侧点数量}$

令$pre[i]$为$a[i]$的前缀和，$p[i]$表示$[1, i]$中已经被选择的右侧点的个数，公式等价于：

$\forall 1\le i< j\le n, p[j]-p[i-1]\le pre[r_j]-pre[l_i-1]$

即:

$\forall 1\le i< j\le n, pre[l_i-1]-p[i-1]\le pre[r_j]-p[j]$

于是可以对每个位置维护一个$pre[l_{i + 1} - 1] - p[i]$和$pre[r_i] - p[i]$，注意此时$i \in [0, n]$

其中$pre[i]$是是定值，$p[i]$可以用线段树轻松维护，每次插入时只需要前检查$i < x$的$pre[l_i-1]-p[i-1]$的最大值和$i \ge x$的$pre[r_j]-p[j]$的最小值的关系即可。