A. Ring

似乎算是一道半原题，原题的做法是维护环上的最小编号边，然后替换。

本题的是否存在环更好维护。

容易发现对于一个左端点，右端点的答案是单调的。

存在一个分界点，满足分界点左侧没有环，分界点右侧有环。

因为单调，所以可以在左端点移动的同时，右端点用单调指针维护分界点的位置。

方法是使用LCT的$link,cut,findroot$操作进行维护。

如果左端点对应的边连接的两个点已经在一个连通块，那么不断$cut$右端点对应的边即可。

B. Exchange

与$zkw$线段树的操作类似，将$n$补为$2^k$的形式，满足$2^k>n$,$2^{k-1}<=n$。

然后发现交换操作对应着线段树上一个节点的更改。

所以直接维护一棵区间修改、区间查询、标记下传、动态开点的线段树即可。

C. Match

首先将方差转化为$\frac{n*val-sum^2}{n^2}$的形式。

其中$val$表示该方案中每一项的平方的和，$sum$表示每一项的线性加和。

考虑通过总和/总方案来算得期望值。

设$f_n$表示$2n$个数，对应的总方案数，显然有$f_n=\prod_{i=1}^n(2*i-1)$。

这个可以通过$dp$转移方程$f_n=f_{n-1}*(2*n-1)$解释，也可以直接按照搜索的思想来。

设$w$表示总和中前一项的贡献。

有$w=f_{n-1}*n*\sum \limits_{i=1}^{2*n-1}(2*n-i)*i^2$。

其中的$(2*n-i)$表示差值为$i$的点对的个数，$i^2$表示贡献。

设$s$表示总和中后一项的贡献。

首先写出$s$的表达式，为$s=\sum \limits_{P}(\sum \limits_{i=1}^nx_i)^2$，其中$P$表示枚举状态。

可以发现这个平方式是可以拆的。

于是变成$s=\sum \limits_{P}(\sum \limits_{i=1}^n\sum \limits_{j=1}^nx_ix_j)$。

于是可以考虑每一对$x_i,x_j$，分别统计贡献。

考虑$i!=j$时的贡献，首先令$s=f_{n-2}(\sum \limits_{i=1}^n(2n-i)i)^2$。

这个式子是错误的。

因为对于跨过了同一个点的情况，是不合法的，也就是没有任何一个$x_i,x_j$满足的。

所以减掉这样的情况，然后发现$i=j$的情况减了两次，所以加回来一次，最后统计$i=j$的情况即可。

因为上面乘的是$f_{n-1},f_{n-2}$，下面除掉$f_{n}$，所以没有必要算出精确值。

容易发现，这堆东西都可以展开成自然数幂和，然后推式子（通过插值偷懒）。

因为这个玩意就是一个简单的多项式，直接通过高斯消元消出系数其实也可以（但是本题存在$n^{-1}$项系数）。