【GDOI2018模拟8.14】神奇的矩阵

本文主要是介绍【GDOI2018模拟8.14】神奇的矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

这里写图片描述

Input

这里写图片描述

Output

输出一行表示答案

Sample Input

3 3 2
1 2 3
4 5 6
7 8 9

Sample Output

112

Solution

真是神奇的一道题
为了避免绝对值的影响，让每个数字从小到大加入，对于每个数字考虑贡献
设f[i][j]表示以(i,j)为左上角的k*k的矩阵中有数的个数
那么一个数在加入时，所有包括它的k*k矩阵的f的和，就是这个数对答案做的正贡献
那么这些矩阵其他的为空的数量就是这个数的负贡献
直接统计即可
f值维护时需要二维区间加和二维区间求值
我用树状数组维护，详细点这里

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define N 510
#define ll long long
#define mo 10007
#define lowbit(x) ((x)&(-x))
using namespace std;
ll a[N][N],ans,n,m,k,c[N][N],t[4][N][N];
ll tot=1;
struct node{ll x,y;
}b[N*N];
bool cnt(node x,node y){return a[x.x][x.y]<a[y.x][y.y];}
ll get(ll z,ll x,ll y)
{ll ans=0;for(ll i=x;i;i-=lowbit(i)) for(ll j=y;j;j-=lowbit(j)) ans+=t[z][i][j];return ans;
}
ll sum(ll x,ll y)
{return (((x+1)*(y+1)*get(0,x,y))%mo-((x+1)*get(2,x,y))%mo-((y+1)*get(1,x,y))%mo+get(3,x,y)+mo+mo)%mo;
}
void put(ll z,ll x,ll y,ll w)
{for(ll i=x;i<=n;i+=lowbit(i)) for(ll j=y;j<=m;j+=lowbit(j)) t[z][i][j]+=w;
}
void ins(ll x,ll y,ll w)
{put(0,x,y,w);put(1,x,y,w*x);put(2,x,y,w*y);put(3,x,y,w*x*y);
}
int main()
{freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&k);fo(i,1,n) fo(j,1,m) scanf("%lld",&a[i][j]),b[(i-1)*n+j].x=i,b[(i-1)*n+j].y=j;sort(b+1,b+n*m+1,cnt);fo(i,1,n*m){ll x=b[i].x,y=b[i].y,x1=max(1,b[i].x-k+1),x2=min(b[i].x,n-k+1),y1=max(1,b[i].y-k+1),y2=min(b[i].y,m-k+1);ll jy=sum(x,y)-sum(x,y1-1)-sum(x1-1,y)+sum(x1-1,y1-1);a[b[i].x][b[i].y]%=mo;x=(x%mo+mo)%mo;(ans+=(a[b[i].x][b[i].y]*((jy-(x2-x1+1)*(y2-y1+1)*((k*k-1)%mo)%mo+jy+mo)%mo))%mo)%=mo;(ans+=mo)%=mo;ins(x1,y1,1);ins(x1,y2+1,-1);ins(x2+1,y1,-1);ins(x2+1,y2+1,1);}printf("%lld",(ans*2)%mo);
}