A
\(n\) 个点的完全图，\(i\to j(i<j)\) 的边权是 \(u_j-u_i\)，问最小生成树。\(n\le 3e5\)。
考虑 boruvka 算法。boruvka 算法是重复以下过程，直到只有一个连通块。
找到所有连通块的连向外面的最小边，并把这些边加入最小生成树。不难发现这是最多做 \(\log n\) 次的。
我们现在考虑这个题，一个连通块假设有 \(m\) 个点，我们直接枚举这 \(m\) 个点做起点的情况。
我们要 ST 表维护区间 RMQ。把连通块 \(m\) 个点的间隔处的区间取出算。
B
你需要执行如下操作：输入一个数 \(x\)，每次把 \(x\) 乘 \(d\)，并判断是否满足 \(n|x\)，是就退出。
给定 \(l,r\)，代表每次修改一个数 \(x\)，都会使得 \(x\gets x+t(t\in[l,r])\)，\(t\) 是等概率随机的。
包括输入，乘法都会被影响。
\(q\) 次询问输入一个数 \(x\)，询问至少要做多少次乘法后退出。
\(n,q\le 1e6\)，\(t\le 10\) 组询问。
考虑建反图。将 \(xd\bmod n+[l,r]\) 的所有数都向 \(x\) 连边。最后从 \(0\) 开始 BFS。
如果使用线段树优化建图，复杂度过大。
考虑使用并查集，维护每个数右边第一个还没有被计算的位置。一开始 \(f_i=i\)。
由于 bfs 满足第一次搜到的一定最优，那么每个点只会被更新一次。
那么我们 bfs，每次更新都是更新一个区间 \([x,y]\) 的点的值。
初始令 \(i=x\)，每次令 \(i\to f_i\) 并更新即可，再 merge \(i\) 和 \(i+1\)，直到 \(i>y\).
C
\(q\) 次询问给定区间 \([l,r]\)，拿出里面的物品做背包，问代价最大的方案数。
\(n\le 2e4,q\le 1e5,m\le 500\)。
分治，复杂度 \(O(n\log nm+qm)\)。
虽然合并背包是 \(O(m^2)\) 的，但是单点查询，枚举其中一个，另一个做前缀 \(\max\) 即可。
D
无向图每条边的权值 \(\in[l_i,r_i]\)，构造一种方案，使得两两边权值不相同·。
且第 \(1\sim n-1\) 条边构成的树是其中一个最小生成树。\(n,m\le 1e5\)。
如果只考虑前 \(n-1\) 条边，那么贪心，按左端点排序，取最左的能取的权值。
考虑非树边，当其连接的树上的路径的边全部取完后，左端点要跟路径最大值取 \(\max\)。
那么我们维护一个堆，按左端点排序，加树边的时候把连接两个连通块的非树边加入堆。