C

算法 1

显然是断掉一些边，剩下的都是链，也就是树。答案是断掉的边数最大值。

枚举断哪些边，判一下连通性，时间复杂度 $O(2^n(n+m))$，期望得分 $10$。

算法 2

可以发现一定有一条边可以删，而且你随便删一条边之后剩下的点对的连通方式就固定了，相当于要求那一段的边都不能删。暴力求出还剩下哪些边可以删即可。所以做法就是枚举断哪条边，然后差分什么的暴力算一下，时间复杂度 $O(n^2)$，期望得分 $25$。

讨论一下可能可以过特殊性质，我也没咋想。

算法 3

可以发现如果按顺序枚举删哪条边，那每个点对 $(x_i,y_i)$ 覆盖的那些边会恰好修改 $O(1)$ 次。一开始覆盖 $[x_i,y_i]$ 之间的边，当枚举到 $x_i$ 时会覆盖 $[1,x_i]$ 和 $[y_i,n]$ 的边，当枚举到 $y_i$ 时会覆盖 $[x_i,y_i]$ 的边。所以考虑使用线段树维护每条边的覆盖次数，相当于要做区间加，问全局有多少个 $0$。直接线段树维护最小值和最小值个数即可。时间复杂度 $O(nq\log n)$，期望得分据实现优秀程度 $65\sim 90$。

算法 4

上面那个做法很难支持修改。我们直接换个做法。

考虑一个 $(x_i,y_i)$ 对删边的限制是什么：对于两条边 $e_1,e_2$，如果它们在 $(x_i,y_i)$ 的同侧（即满足 $x_i\le e\le y_i$ 同时满足或同时不满足），则可以同时删或者同时不删；如果在异侧，则不能同时删。

这启发我们给每条边一个 01 串：$s_{i,j}$ 表示边 $i$ 在区间 $[x_j,y_j]$ 里侧还是外侧。可以发现当且仅当 $s_i=s_j$ 时才能同时删边 $e_i,e_j$（否则表示对于某一个点对 $(x,y)$，两条边在异侧）。所以答案相当于 $s_i$ 的桶的最大值（最多多少个 $s_i$ 两两相等）。直接维护大概可以做到 $O(n(n+q)\log n)$，但是忘了给分了。

注意我们相当于要维护一个下标为 $s_i$ 的 map。考虑 xor hash 来把字符串转化成一个整数。对每个点对 $(x_i,y_i)$ 随机一个 $[C,2^{64}-C]$ 的变量 $a_i$，然后记一条边的权值 $w(e_i)=\oplus [s_{i,j}=1]a_j$，也就是所有 $x_j\le e_i\le y_j$ 的 $a_j$ 的异或和。这个相当于每个 $(x,y)$ 把区间内异或上随机变量。转化成整数之后再 map。错误率我也不会分析，应该非常低。

这个说人话就是使用 xor hash 之后 $s$ 的修改量是 $O(1)$ 的（只修改一位 $s_{i,j}$）。

这个也非常容易维护待修。因为修改量是 $O(1)$ 的，相当于哈希值改变的只有 $1$ 个元素，稍微写点讨论就好了。时间复杂度 $O((n+q)\log n)$，期望得分据实现优秀程度 $95\sim 100$。写不到 $100$ 的话常数堪忧啊。