c题jls的代码，拿过来仔细研究了一番，终于弄明白了。
https://codeforces.com/contest/1859/problem/C
jls代码

#include <bits/stdc++.h>

using i64 = long long;
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
void solve() {
    int n;
    std::cin >> n;
    
    int ans = 0;
    for (int l = n * n; ; l--) {
        DSU dsu(n + 1);
        int sum = 0;
        bool ok = true;
        for (int i = n; i >= 1; i--) {
            int x = dsu.find(std::min(n, l / i));
          // std::cerr<<l<<" "<<i<<" "<<x<<'\n';
          // std::cerr<<dsu.f[x]<<"\n";
          
            if (x == 0) {
                ok = false;
                break;
            }
            sum += i * x;
            dsu.merge(x - 1, x);
             //std::cerr<<dsu.f[x]<<"\n";
        }
        if (!ok) {
            break;
        }
        ans = std::max(ans, sum - l);
    }
    
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

c++一秒钟大约能跑\(4 * 10 ^ 8\)次，本题数据范围到500，\(O(n^3logn)\)理论上是能过的（~~当然会被卡常~~），

为了防止痛苦，我们可以学习上面代码用并查集来维护当前情况排列的连通性，把复杂度降到\(O(n^3)\)。
首先值得学习的是DSU的板子，其次是这道题是如何用dsu来维护的，为什么能用dsu维护，这可以使我们对dsu的理解加深，

算法综述：本题常规解法是枚举可能的最大成本值，然后枚举每个位置的取值，根据cf题解的证明，每个位置的成本都应该尽可能接近最大值，但这就产生了竞争，但可以通过反证法证明越靠后的位置应该优先选数，因为优先选才能选到大数，这样可以使成本最高，所以我们倒序遍历每个位置。

先对上面这段话举个例子，比如现在到第3个数选了，由于其位置靠前，本来可以选很多大数，但是由于它在后面选，所以它只能选剩下的数中较大的数。

继续算法分析：在遍历每个位置时侯，我们先看如果没有任何限制这个位置最大能取什么数,这个数记作x，当然肯定要min(n,x），如果这个数已经被用过了，那么就去找次大的数，以此类推，直到发现这个位置能取的数都已经被抢完了，那说明当前这个最大值无法形成最优排列，我们直接break。如果为这个位置找到了当前视角下的最优数，我们将其加入排列，维护sum和排列。

上述算法描述如何实现呢？这个实现方式是关键，
容易想到的用set维护，维护当前哪些数能用，并且set是有序容器，且可以二分，这些将在下一份代码中作进一步展开。
完全想不到用并查集来维护，维护方式如下；

首先是dsu初始化已经完成,直接x=find(min(n, mx/ i)),只要x!=0,就说明能为当前这个位置找到数，然后merge合并操作将x的父节点指向x-1。

为什么将x的父节点指向x-1？

我们需要让后序的位置找到他们的最优数，比如后面也有一个位置想要x,但我们知道x已经用过了，但通过find我们可以找到x-1，x-1是次优数，后续同理，可以不断向前找。

为什么x==0就这个位置说明找不到了呢？

由于是逆序枚举位置，find函数传入的参数肯定是越来越大，而x一定是不断减1，所以之前的父节点又成为别人的子节点，而由于find函数是经过路径压缩的，所以一个连续用过的序列所有点都一定是指向其中的最小值的，当1也被用完，merge成为0的子节点时，比如此时1，2，3已经用过，而目前位置下一个数只能取<=3的数，一次find操作后会让1，2，3都指向0，所以当发现x==0的时候就说明当前这个排列无法构建了！