JZOJ 5270 神奇的矩阵

首先考虑怎么去绝对值（这套题前两题都用到了这个套路），按大小插入计算贡献即可。

考虑将所有数排序，然后维护每个点作为左上角的矩阵中目前插入了多少个数。
对于每个点，包含当前点的所有矩阵的左上角同样构成一个子矩阵，于是查询这些矩阵目前共有多少个数，可以得到当前点对答案的贡献，然后矩阵上修改即可。
使用二维树状数组维护矩阵加矩阵和。

代码：

#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
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);
}