题意

给定一个 $n$ 行的数组，第 $i$ 行有 $i$ 个元素，保证 $[1,\frac{n(n+1)}2]$ 各出现一次。取 $n$ 轮数，$a_{i,j}$ 只能在第 $j$ 轮到第 $i$ 轮被取，求取出的元素和最大值。$n\le 2000$。

题解

对于任意一个解，若存在 $a_{i,j}$ 比 $[j,i]$ 区间内某元素大，则一定可以替换得到更优解。因此只需维护当前答案集合 $S$，从大到小尝试加入每个值 $x$，若 $S\cup\{x\}$ 可均在答案内则保留，最终得到的 $S$ 即为最优解。这样若 $a_{i,j}$ 不在答案内，说明答案的 $[j,i]$ 区间均大于 $a_{i,j}$，于是该做法正确。

现需判断 $S$ 集合均在答案内是否合法，注意到操作与数字之间的关系类似匹配，考虑 Hall 定理，需满足 $\forall T\subseteq S,\left|T\right|\le \left|\bigcup_{x\in T}[l_x,r_x]\right|$，其中 $l_{a_{i,j}}=j,r_{a_{i,j}}=i$。此时右式必为若干段区间，根据抽屉原理若 $T$ 不合法，则必然存在一段区间不合法。于是只需考虑右式为区间的限制，有 $\forall L\le R,\sum_{x\in S}[L\le l_x\le r_x\le R]\le R-L+1$，即任意区间 $[L,R]$ 的子区间数量不超过区间长度。

若每次加入时暴力判断，朴素实现是 $\mathcal O(n^4)$ 的。可移项得到 $R-L+1-\sum_{x\in S}[L\le l_x\le r_x\le R]\ge 0$，将区间画到平面上，在每个点上维护该值，则 $x$ 会将 $(l_x,r_x)$ 左上角的点权值减一，能否加入也取决于这部分是否存在零。于是只需求出每行首个零的位置 $p_i$，只有 $\min_{i=r_x}^n p_i\gt l_x$ 时能加入 $x$。由于加入只有 $n$ 次，每次对若干行前缀减一后求出新的 $p$ 并做后缀 $\min$，即可 $\mathcal O(1)$ 判断能否加入。直接使用线段树进行前缀减，维护全局最小值及位置即可做到 $\mathcal O(n^2\log n)$，构造方案随便贪心一下就行，实现好一点是能过的。

题解区还有 JoeyJ 的做法，这里给出比较详细的解释。令 $b_i$ 表示目前第 $i$ 轮操作的取值。考虑每次从 $v=x,p=l_x$ 开始，若当前 $b_p=0$ 则填上 $v$，否则比较 $r_v$ 和 $r_{b_p}$，将较小的留在 $p$ 位置，并以另一个为新的 $v$，最后 $p\leftarrow p+1$。若直到 $p\gt r_v$ 还没填完则说明 $x$ 无法填入，放弃填 $x$ 并将 $b$ 数组还原；否则保留得到的 $b$ 数组即可。

这样得到的序列 $b$ 一定合法，还需证明所有合法序列均能构造出来。设 $p_x$ 表示 $x$ 在 $b$ 中的位置，即 $b_{p_x}=x$，有 $\forall x\in b,\forall i\in[l_x,p_x],b_i\ne 0,r_{b_i}\le r_x$。刚加入 $x$ 时根据构造过程显然满足，且之后 $r_y\gt r_x$ 的 $y$ 跳到 $l_x$ 处时，由于该区间内均满足 $r_{b_i}\le r_x\lt r_y$，其一定不会留在该区间内，于是该结论成立。

接着考虑若最终无法填入 $x$，说明最后一个 $v$ 满足 $[l_x,r_v]$ 内全满且 $r_{b_i}\le r_v$。此时以 $[l_x,r_v]$ 为初始区间 $[L,R]$，每次更新 $L\leftarrow \min_{i=L}^R l_{b_i}$ 直到不再改变。根据上一段的结论，此时 $[L,R]$ 内必然全满且 $\forall i\in[L,R],L\le l_{b_i}\le r_{b_i}\le R$，于是加入 $x$ 会导致 $[L,R]$ 区间在 Hall 定理下不合法。这样就证明了该过程下无法加入与 Hall 定理不合法等价，于是正确性有保证了，朴素实现复杂度 $\mathcal O(n^3)$。

考虑使用与上种做法相同的思路优化，即实现 $\mathcal O(1)$ 判断 $x$ 能否加入。设 $lim_i$ 表示 $l_x=i$ 时 $x$ 能加入需要的最小 $r_x$，若 $b_i=0$ 或 $r_{b_i}\ge lim_{i+1}$ 有 $lim_i=i$，否则 $lim_i=lim_{i+1}$，可以 $\mathcal O(n)$ 预处理。这样 $n$ 次加入新元素时重新预处理，即可 $\mathcal O(1)$ 判断能否加入，总复杂度 $\mathcal O(n^2)$。

参考实现

第一种做法：

#include<bits/stdc++.h>
#define lc (u<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define Lc lc,l,mid
#define Rc rc,mid+1,r
using namespace std;
const int N=2010;
const int M=N*(N+1)/2;
struct SG
{
    short w[N<<2],p[N<<2],tag[N<<2];
    void pushup(int u) {w[u]=min(w[lc],w[rc]),p[u]=p[w[u]==w[lc]?lc:rc];}
    void pt(int u,int x) {tag[u]+=x,w[u]+=x;}
    void pushdown(int u) {if(tag[u]) pt(lc,tag[u]),pt(rc,tag[u]),tag[u]=0;}
    void build(int u,int l,int r,int R)
    {
        if(l==r) {w[u]=R-l+1,p[u]=l; return;}
        build(Lc,R),build(Rc,R),pushup(u);
    }
    void update(int u,int l,int r,int R)
    {
        if(r<=R) {pt(u,-1); return;}
        pushdown(u);
        if(R<=mid) update(Lc,R);
        else pt(lc,-1),update(Rc,R);
        pushup(u);
    }
}T[N];
int n,m,cc,lim[N]; short l[M],r[M]; long long res;
struct nod{int x,l,r;}a[N];
bool cmp(nod A,nod B) {return A.l<B.l;}
priority_queue <pair<int,int> > Q;
void ini()
{
    lim[n+1]=n+1;
    for(int i=n;i;i--) lim[i]=min(lim[i+1],T[i].w[1]?n+1:T[i].p[1]);
}
void solve(int tn,vector<vector<int>> A,long long& answer,vector<int>& solution)
{
    n=tn,m=n*(n+1)/2;
    for(int i=1;i<=n;i++)
    {
        T[i].build(1,1,i,i);
        for(int j=1,x;j<=i;j++) x=A[i-1][j-1],l[x]=j,r[x]=i;
    }
    ini();
    for(int i=m;i;i--) if(lim[r[i]]>l[i]) 
    {
        for(int j=r[i];j<=n;j++) T[j].update(1,1,j,l[i]);
        ini(),res+=i,a[++cc]={i,l[i],r[i]};
    }
    answer=res,sort(a+1,a+1+cc,cmp),solution.clear();
    for(int i=1,tp=1;i<=n;i++)
    {
        while(tp<=cc&&a[tp].l==i) Q.push({-a[tp].r,a[tp].x}),tp++;
        solution.push_back(Q.top().second),Q.pop();
    }
}

第二种做法：

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
const int M=N*(N+1)/2;
int n,m,l[M],r[M],lim[N],res[N]; long long rs;
void solve(int tn,vector<vector<int>> A,long long& answer,vector<int>& solution)
{
    n=tn,m=n*(n+1)/2,lim[n+1]=n+1;
    for(int i=1;i<=n;i++)
    {
        lim[i]=i;
        for(int j=1,x;j<=i;j++) x=A[i-1][j-1],l[x]=j,r[x]=i;
    }
    for(int i=m;i;i--) if(lim[l[i]]<=r[i])
    {
        int v=i,p=l[i]; rs+=v;
        while(res[p])
        {
            if(r[v]<r[res[p]]) swap(res[p],v);
            p++;
        }
        res[p]=v;
        for(int i=n;i;i--) lim[i]=(!res[i]||r[res[i]]>=lim[i+1]?i:lim[i+1]);
    }
    answer=rs,solution.clear();
    for(int i=1;i<=n;i++) solution.push_back(res[i]);
}