「LibreOJ β Round #3」绯色 IOI（悬念） 题解

zrl123456 · 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