本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 11:32:38

:::::info[题目基本信息] 考察：二分图，基环树，线段树（个人认为上位紫）。
题目简介：
给定一个由 $n$ 个左部点（编号为 $0$ 到 $n-1$，保证 $n$ 是奇数）和 $m$ 个右部点（编号为 $0$ 到 $m-1$）构成的二分图，$i$ 号左部点和 $j$ 号右部点右边当且仅当 $\min((j-a_i)\bmod n,(a_i-j)\bmod n)=b_i$（其中 $\{a_m\},\{b_m\}$ 事先给定，且 $\bmod$ 运算结果取最小的非负整数），将边编号（按左部点编号从小到大为第一关键字，按右部点编号从小到大为第二关键字），并给定每条边的初始权值 $w_i$，有 $q$ 次操作，每次操作将编号为 $pos_i$ 的边的权值改为 $v_i$，求所有操作前及每次操作后的二分图最大权完全匹配（保证存在），可能强制在线。
数据范围：

• $1\le m\le n\le 5\times 10^5$
• $\forall i\in[0,m),0\le a_i<n$
• $\forall i\in[0,m),0\le b_i\le\lfloor\frac{n}{2}\rfloor$
• $0\le q\le 8\times 10^5$
• $\forall i\in[1,2m-\sum_{j=0}^{m-1}[b_j=0]],0\le w_i\le 1300$
• $\forall i\in[1,q],1\le pos_i\le 2m-\sum_{j=0}^{m-1}[b_j=0]$
• $\forall i\in[1,q],0\le v_i\le 1300$ ::::: 注意到这个图上每个左部点的度最多为 $2$，所以肯定有特殊性质，这就是一个经典 trick：在两个点间连边（若一左部点只有一个度那就是一个自环）。
  但是怎么存储选择哪个点这一信息呢？注意到我们可以钦定它为有向边，那么它所指向的点就是左部点选择的点，这时每个右部点要求入度最多为 $1$，左部点的作用到此为止。
  那么这样转化有什么好处呢？
  由于保证存在完美匹配所以一个联通块的边数不能大于点数，同时由于它联通那么一个连通块要么是基环树，要么是树，现在我们分两种情况讨论：
• 基环树：
  我们贪心地想，我们不能浪费度为 $1$ 的点，这样最后就搞不出来完美匹配了，那么与它相连的边只能指向它，那么我们删去与它相连的边和它递归下去，最终会剩下一个环。
  对于一个环，我们想让它存在完美匹配那么只能全顺时针连和全逆时针连，同时维护外向边的权值和、环内顺时针边的权值和、环内逆时针边的权值和即可。
• 树：
  这时会有一个点不被选择，不妨枚举不被选择的点 $u$，最后会变成以 $u$ 为根的一棵外向树，我们随便默认一个点为根，那么对于一条边，当它是从上往下指的时候不位于下方点的子树内时会贡献答案，当它是从下往上指的时候位于下方点的子树内的时候会贡献答案，在预处理时把 DFS 序跑出来然后线段树区间修改区间求 $\max$ 即可。

然后我们就做完了这道题。
时间复杂度为 $\Theta(n+(m+q)\log n)$，空间复杂度为 $\Theta(n+m)$。

code