CF2053F Earnest Matrix Complement
题意：
多测
每次给定 \(n,m,k\) ，存在一个 \(n \times m\) 的表格，其中 \(a_{i,j} \in {[1,k]\ \text{and}\ -1}\)
令 \(c_{i,j} = \sum_{p = 1}^m {[a_{i,p} = j]}\)
最后 \(V = \sum_{i = 2}^n \sum_{j = 1}^{n \times m} c_{i - 1,j} \times c_{i,j}\)，你可以为每个 \(-1\) 分配一个数字，求最大的 \(V\)
\(\sum n\times m \leq 6\times 10^5,k \leq n\times m\)
观察一：每行的 \(-1\) 只会填同一个数。
我们这里只简单考虑两行的情况，且两行只有 \(1/2\) 两种颜色，更复杂的情况可以从这里进行推知。
我们考虑第一行的涂色情况为 \(c_{1,1} = p_1,c_{1,2} = p_2\)
那么我们考虑第二行的涂色情况，\(c_{2,1} = x,c_{2,2} = m - x\)
\(V = p_1 \times x + p_2 \times (m - x) = (p_1 - p_2)\times x + p_2 \times m\)
容易知道这个函数肯定最值取在一端，于是推知每行的 \(-1\) 只会填一个数。
对于更复杂的情况，可以通过每次合并两种颜色来进行处理推至。
基于这个观察，我们容易写出一个 \(dp\) 式子。
令 \(f_{i,x}\) 为第 \(i\) 行涂 \(x\) 颜色所取得的最大值
我们容易写出转移式 \(f_{i,x} = \max_{y} f_{i - 1,y} + \text{conv(i,x,y)}\)
这里 \(\text{conv(i,x,y)}\) 表示第 \(i\) 行涂 \(x\) ，上一行涂 \(y\) 的贡献
于是我们得到了一个 \(O(nk)\) 复杂度的转移式。
我们先回顾我们所得到的结论，我们 \(dp\) 柿子应该是写的非常正确的，我们想要优化，只能尝试从 \(\text{conv(i,x,y)}\) 上来得到了
我们将 \(\text{conv}(i,x,y)\) 展开书写
这里我们令
\(nc_{i,c}\) 表示不计算 \(-1\) 在内的第 \(i\) 行的 \(c\) 的数量
\(p_i\) 表示第 \(i\) 行的 \(- 1\) 数量
\(\text{conv(i,x,y)} = \sum_{c \neq x \ \text{and}\ c \neq y} nc_{i - 1,c} \times nc_{i,c} + (nc_{i - 1,y} + p_{i - 1}) \times nc_{i,y} + (nc_{i,x} + p_{i}) \times nc_{i - 1,x} + [x = y]p_{i - 1}\times p_{i} - [x = y] nc_{i,x} \times nc_{i - 1,y}\)
把贡献拆分开来，将贡献分为三部分，一部分来自于两边都是确定的颜色，一部分来自于一边确定一边不确定，一部分来自于两边都不确定
\(\text{conv(i,x,y)} = \sum_{c} nc_{i - 1,c} \times nc_{i,c} + p_{i - 1} \times nc_{i,y} + p_{i} \times nc_{i - 1,x} + [x = y]p_{i - 1}\times p_{i}\)
\(\text{conv(i,x,y)} = W + p_{i - 1} \times nc_{i,y} + p_{i} \times nc_{i - 1,x} + [x = y]p_{i - 1}\times p_{i}\)
形式一下变得优美太多。
考虑我们在转移的时候如何操作呢
这里柿子的第二项表示如果我们从 \(f_{i-1,y}\) 转移到 \(f_{i,x}\) 会加上 \(p_{i - 1} \times nc_{i,y}\)
这里柿子的第三项表示我们 \(f_{i,x}\) 需要加上 \(p_{i} \times nc_{i - 1,x}\)
第四项表示若 \(f_{i - 1,x}\) 转移到 \(f_{i,x}\) 需要额外加上 \(p_{i - 1} \times p_i\)
于是我们改写原本的转移方程 \(f_{i,x} = \max_y f_{i - 1,y} + \text{conv(i,x,y)} = W + p_i \times nc_{i - 1,x} + \max {(f_{i - 1,y} + p_{i - 1} \times nc_{i,y} + [x = y]p_{i - 1} \times p_{i})}\)
我们把 \(x = y\) 的情况特殊写出来
\(f_{i,x} = W + p_i \times nc_{i - 1,x} + \max(f_{i - 1,x} + p_{i - 1} \times nc_{i,x} + p_{i - 1} \times p_{i},\max {(f_{i - 1,y} + p_{i - 1} \times nc_{i,y}))}\)
我们回顾这个柿子，其中 \(nc_{i,y}\) 只在 \(y \in S_i\) 中不为 0，我们可以枚举这些颜色，然后先处理出 \(\max(f_{i - 1,y} + p_{i - 1} \times nc_{i,y}) = rmax\)
接着我们发现第一项这里等价于，先给所有位置都加上 \(p_{i - 1} \times p_i\)，再枚举所有颜色，为 \(f_{i - 1,x}\) 加上 \(p_{i - 1} \times nc_{i,x}\)
最后对所有位置，对 \(rmax\) 取 \(\max\)
然后同样的，我们最后对所有位置加 \(W\)，然后对有值的 \(p_i \times nc_{i - 1,x}\) 加上即可。
于是我们回顾我们的操作，我们需要支持一个 全局加，单点加，全局取 \(\max\)，查询全局 $\max $
我们当然可以直接随便上个吉司机线段树。
这里提供一个线性实现的做法，我们维护这样一个数据结构 \(f_i = \max(a_i + add,tmax)\)
我们每次全局加时令 \(add\) 和 \(tmax\) 同时加
全局取 \(max\) 则取 \(tmax = maxx\)
单点加时，我们发现我们一直加的是一个正数，也就是我们实际上加完就不用管目前的取 \(max\) 限制了，于是我们直接令 \(a_i = f_i + b - x\) 即可
实际上就是标记永久化了一下。
维护全局 \(max\) 就顺手维护一下即可。
//画楼云雨无凭
#include<bits/stdc++.h>
#define ll long long
#define N 600005
int n,m,k;
int nexmax;
//f_{i,j} = \max(w + )
struct P{
ll adtag = 0;
ll mxtag = 0;
ll nmax = 0;
ll f[N];
void clear(){
for(int i = 0;i <= n * m;++i)f[i] = 0;
adtag = mxtag = nmax = 0;
}
void cover_ad(ll x){
nmax += x;
adtag += x;
mxtag += x;
}
ll get(int ind){return std::max(f[ind] + adtag,mxtag);}
void cover_mx(ll mx){
nmax = std::max(nmax,mx);
mxtag = std::max(mxtag,mx);
}
void change_ad(int ind,ll x){
ll res = std::max(f[ind] + adtag,mxtag);
ll to = res + x;
f[ind] = to - adtag;
nmax = std::max(nmax,to);
}
ll get_mx(){return nmax;}
}T;
int c[N];
int a[N];
using std::map;
map<int,int>cnt[N];
inline void solve(){
scanf("%d%d%d",&n,&m,&k);
T.clear();
for(int i = 1;i <= n;++i)c[i] = 0,cnt[i].clear();
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
scanf("%d",&a[j]);
if(a[j] == -1)c[i] ++ ;
else cnt[i][a[j]] ++ ;
}
}
for(int i = 2;i <= n;++i){
ll c0 = c[i - 1],c1 = c[i];
ll rmax = T.get_mx();
ll w = 0;
for(auto [x,_] : cnt[i - 1]){if(cnt[i].find(x) != cnt[i].end()){w = w + 1ll * cnt[i - 1][x] * cnt[i][x];}}
for(auto [y,_] : cnt[i]){rmax = std::max(rmax,1ll * c0 * cnt[i][y] + T.get(y));}
T.cover_ad(1ll * c0 * c1);
for(auto [y,_] : cnt[i]){T.change_ad(y,1ll * c0 * cnt[i][y]);}
T.cover_mx(rmax);
T.cover_ad(w);
for(auto [x,_] : cnt[i - 1]){T.change_ad(x,1ll * cnt[i - 1][x] * c1);}
}
std::cout<<T.get_mx()<<"\n";
}
int main(){
int _ = 1;
scanf("%d",&_);
while(_ -- ){
solve();
}
}