我在讲这道题目的时候，机房大神问我，不是直接并查集就行了吗，我思考着题解的可撤销并查集陷入了沉思。很显然，我的大脑过载了。 但是这样写确实是对的，直接并查集合并就行，没必要撤销，无法理解题解所说的。 核心代码： ```cpp void solve(int l, int r, vector &v) { if (v.emp…

这个数据生成器可以生成答案为 YES 的数据 ```cpp #include #include #include #include using namespace std; #define ll long long #define pii pair mt19937 ci(time(0)); const int N =…

```cpp inline void link(int x, int y) { int fx = find(x), fy = find(y); split(y, x); // makeroot(y); 不能这样写，splay中不把y提到根，上面的标记会影响link fa[y] = x, vs[x] += s[y]; f…

和原题的区别是这道题目缩小了n，增加了k的范围，但是n缩小之后导致满足条件的数字最多只有2682562个，所以任意的暴力搜索都可以通过（bfs/dfs）！！

https://www.cnblogs.com/The-Shadow-Dragon/p/18650825 https://www.cnblogs.com/maoyiting/p/14178833.html

~~我是小菜鸡 Div.2 rk60+~~ 通过模拟我们可以发现一下几个性质。 我们设 $a$ 的值域为 $V$。 1. $f[l, r]$ 不大于 $f[l - x, r] , x > 0$。 2. 任意 $f[l, r]$ 不大于 $2\log(V)≤128$。 3. 总有一个最优解，**只使用成本最多为 $3$…