首先考虑怎么去绝对值（这套题前两题都用到了这个套路），按大小插入计算贡献即可。
考虑将所有数排序，然后维护每个点作为左上角的矩阵中目前插入了多少个数。
对于每个点，包含当前点的所有矩阵的左上角同样构成一个子矩阵，于是查询这些矩阵目前共有多少个数，可以得到当前点对答案的贡献，然后矩阵上修改即可。
使用二维树状数组维护矩阵加矩阵和。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
const int N = 500;
const int mod = 1e4 + 7;
int n,m,k,tot;
int ans;
struct note
{
int v,x,y;
inline bool operator<(const note &o) const
{
return v < o.v;
}
} a[N * N + 5];
int c[4][N + 5][N + 5];
inline void update(int x,int y,int k)
{
for(register int i = x;i <= n;i += lowbit(i))
for(register int j = y;j <= m;j += lowbit(j))
c[0][i][j] = (c[0][i][j] + k) % mod,
c[1][i][j] = (c[1][i][j] + k * x) % mod,
c[2][i][j] = (c[2][i][j] + k * y) % mod,
c[3][i][j] = (c[3][i][j] + k * x % mod * y) % mod;
}
inline int query(int x,int y)
{
int ret = 0;
for(register int i = x;i;i -= lowbit(i))
for(register int j = y;j;j -= lowbit(j))
ret = (ret
+ c[0][i][j] * (x + 1) % mod * (y + 1) % mod
- c[1][i][j] * (y + 1) % mod + mod
- c[2][i][j] * (x + 1) % mod + mod
+ c[3][i][j]) % mod;
return ret;
}
int main()
{
freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf("%d",&a[++tot].v),a[tot].x = i,a[tot].y = j;
sort(a + 1,a + tot + 1);
for(register int i = 1;i <= tot;++i)
{
int x1 = max(a[i].x - k + 1,1),y1 = max(a[i].y - k + 1,1);
int x2 = min(a[i].x,n - k + 1),y2 = min(a[i].y,m - k + 1);
int sum = (query(x2,y2) - query(x1 - 1,y2) + mod - query(x2,y1 - 1) + mod + query(x1 - 1,y1 - 1)) % mod;
a[i].v %= mod;
ans = (ans + a[i].v * (sum - (x2 - x1 + 1) * (y2 - y1 + 1) % mod * (k * k % mod - 1 + mod) % mod + sum + mod) % mod) % mod;
update(x1,y1,1),update(x2 + 1,y1,mod - 1),update(x1,y2 + 1,mod - 1),update(x2 + 1,y2 + 1,1);
}
printf("%d\n",(ans << 1) % mod);
}