题解：CF761F Dasha and Photos
lyh0217
·
·
题解
题目传送门
我们设 $a$ 为原矩阵，$f_{i,j,k}$ 表示将 $(i,j)$ 改为 $k$ 时产生的距离贡献，$f2_{i,j}$ 表示所有矩阵和原矩阵产生的贡献，我们令 $cnt_{i,j,k}$ 表示有几个矩阵将 $(i,j)$ 改为了 $k$，$cnt2_{i,j}$ 表示有几个矩阵覆盖了 $(i,j)$，则：
$$f_{i,j,k}=\left|a_{i,j}-k\right|\times (k-cnt2_{i,j})+\sum_{col=1}^{26}\left|col-k\right|\times cnt_{i,j,col}$$
$$f2_{i,j}=\sum_{col=1}^{26} cnt_{i,j,col}\times \left|a_{i,j}-col\right|$$
显然 $cnt$ 和 $cnt2$ 都可以差分处理，再考虑每个的答案为多少。
对于第 $i$ 个方格，设其修改矩阵的左上角的坐标为 $(x1_i,y1_i)$，右下角的坐标为 $(x2_i,y2_i)$，修改的颜色为 $p_i$。
- 对于被矩阵覆盖了的部分，答案为 $\sum\limits_{j=x1_i}^{x2_i}\sum\limits_{k=y1_i}^{y2_i}f_{j,k,p_i}
- 对于没有被矩阵覆盖的部分，答案为 \sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}f2_{j,k}-\sum\limits_{j=x1_i}^{x2_i}\sum\limits_{k=y1_i}^{y2_i}f2_{j,k}
注意到绝对值是可以动态维护的，所以我们可以正着反着扫一遍，然后处理即可，时间复杂度 $\mathcal{O}(Vnm)$（$V$ 含义同上），具体实现详见代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long qzh[1005][1005][27],qzh1[1005][1005];
int qzh2[1005][1005][27];
int xx[300005],yy[300005],xxx[300005],yyy[300005],c[300005],a[1005][1005];
long long sum(int x,int y,int u,int v,int col)
{
return qzh[u][v][col]-qzh[u][y-1][col]-qzh[x-1][v][col]+qzh[x-1][y-1][col];
}
long long sum2(int x,int y,int u,int v)
{
return qzh1[u][v]-qzh1[u][y-1]-qzh1[x-1][v]+qzh1[x-1][y-1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char ch;
cin>>ch;
a[i][j]=ch-'a'+1;
}
}
for(int i=1;i<=k;i++)
{
cin>>xx[i]>>yy[i]>>xxx[i]>>yyy[i];
char ch;
cin>>ch;
c[i]=ch-'a'+1;
qzh2[xx[i]][yy[i]][c[i]]++;
qzh2[xxx[i]+1][yyy[i]+1][c[i]]++;
qzh2[xxx[i]+1][yy[i]][c[i]]--;
qzh2[xx[i]][yyy[i]+1][c[i]]--;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int p=1;p<=26;p++)
qzh2[i][j][p]+=qzh2[i-1][j][p]+qzh2[i][j-1][p]-qzh2[i-1][j-1][p];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
long long summ=0,tot=0;//tot记录前面或后面有多少个数，summ记录贡献
for(int p=1;p<=26;p++)
{
qzh[i][j][p]+=summ;
summ=summ+qzh2[i][j][p]+tot;
tot+=qzh2[i][j][p];
}
summ=0;
tot=0;
for(int p=26;p>=1;p--)
{
qzh[i][j][p]+=summ;
summ=summ+qzh2[i][j][p]+tot;
tot+=qzh2[i][j][p];
}
for(int p=1;p<=26;p++)
{
qzh[i][j][p]+=(k-tot)*abs(a[i][j]-p);
qzh1[i][j]+=qzh2[i][j][p]*abs(a[i][j]-p);//记录当前矩阵外的答案的前缀和
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int p=1;p<=26;p++)
qzh[i][j][p]+=qzh[i-1][j][p]+qzh[i][j-1][p]-qzh[i-1][j-1][p];
qzh1[i][j]+=qzh1[i-1][j]+qzh1[i][j-1]-qzh1[i-1][j-1];
}
}
long long minn=(long long)1e18,y=0;
for(int i=1;i<=k;i++)
{
long long sum=sum(xx[i],yy[i],xxx[i],yyy[i],c[i])+qzh1[n][m]-sum2(xx[i],yy[i],xxx[i],yyy[i]);
if(minn>sum)
{
minn=sum;
y=i;
}
}
cout<<minn;
return 0;
}
```
[记录](https://codeforces.com/contest/761/submission/337087709)