前言
T3挂没了，此记。
A
AT_chokudai_S002_k
考虑建图，发现如果一个联通块存在环就可以全部贡献，否则只能贡献联通块大小 \(-1\)。
直接算就行。
B
P10116
拆贡献，依次对每个出现的位置的方案进行累加。
发现无论序列出现在哪里，方案数都是一样的，直接算钦定位置后的方案乘上 \(n-m+1\) 即可。
首先留出 \(m\) 次操作给 \(m\) 个位置最后做，剩余操作取值任意，有 \(k^{q-m}\) 种方案。
则我们要求满足条件的操作下标序列的方案数，使得下标 \(1\sim m\) 各至少出现一次。
考虑容斥，钦定 \(i\) 个位置没被选，则方案数为 \(C_{m}^i\times (n-i)^q\)。
故答案为
C
P8476
设 \(f_{i,j}\) 表示考虑到 \(i\) 位置，\(b_i=j\) 的最小值。
发现最优解下必定 \(\forall i,\exist j,a_j=b_i\)。
记对 \(a\) 排序后的数组为 \(c\)。
于是改变状态，设 \(f_{i,j}\) 表示到 \(i\) 位置，\(b_i=c_j\) 的最小值。
设 \(g_{i,*}\) 表示 \(f_{i,*}\) 的后缀最小值，于是
考虑从 \(g_{i-1,*}\to g_{i,*}\) 有什么变化。
设 \(c_k=a_i\)。
若 \(j<k\)，则 \(g_{i,j}=g_{i-1,j}+C\)。
否则 \(g_{i,j}=g_{i-1,j}+c_j-c_k\)。
发现前者是区间加，后者是区间减+区间加 \(a_i\)。
发现 \(c_j\) 与 \(g_{i,*}\) 均单调不降，于是 \(g\) 操作后被分成了两段单调不降的序列。
取后缀 \(\min\) 直接二分+区间覆盖。
上述所有操作均可线段树。