OI题解 - 矩阵操作（省选十连测） | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 矩阵操作（省选十连测）

发表于 分类于 Valine：

搬旧博客到新电脑失败……重新搭了一个？

# 题面

对于一个 $k\times k$ 的矩阵 $A$，定义 $Iv(A)$：

现给定 $n\times n$ 的矩阵 $B$ 和正整数 $m$。求 $B$ 的每个大小为 $m\times m$ 的子矩阵 $B’$ 的 $Iv(B’)$ 之和，对 $10007$ 取模。

> 数据规模：$n\le 500$；$B_{i,j}\le10^4$

# 解析

比较麻烦的是绝对值，于是想到可以先把所有 $B_{i,j}$ 从小到大排序，设排序后为 $B_{x_1,y_1},B_{x_2,y_2},\cdots,B_{x_{n^2},y_{n^2}}$。

那么可以这样计算：

其中 $F_{(x_i,y_i),(x_j,y_j)}$ 表示有多少个子矩阵中同时包含 $(x_1,y_1),(x_2,y_2)$，正确性显然。

可以知道：

  1. 当 $i\le j$ 时：$|B_{x_i,y_i}-B_{x_j,y_j}|=B_{x_j,y_j}-B_{x_i,y_i}$
  2. 当 $i>j$ 时：$|B_{x_i,y_i}-B_{x_j,y_j}|=B_{x_i,y_i}-B_{x_j,y_j}$

于是上面的式子可以换个写法：

相当于把 $B_{x_i,y_i}$ 的贡献拆成了 $+B_{x_i,y_i}$ 的部分和 $-B_{x_i,y_i}$ 的部分（实际上还有 $i=j$ 的情况，但是贡献为 $0$，就不管了）。

于是就需要对于每一个 $i$，快速地计算上式中的两个 $F$ 的求和式。

可以想到从小到大枚举 $i$，维护 $\sum_{j=1}^{i-1}F_{(x_i,y_i),(x_j,y_j)}$。问题转换为一种“矩形框点”的经典问题。考虑把一个 $m\times m$ 的子矩阵用它的右下角坐标表示，那么能框住点 $(x,y)$ 的矩形为 $\left(\max\{x,m\},\max\{y,m\}\right)\to\left(\min\{x+m-1,n\},\min\{y+m-1,n\}\right)$。如下图（两个橙色 $4\times4$ 的矩形为能框住蓝色位置的最靠左上的矩形和最靠右下的矩形；红色区域是能框住蓝色位置的矩形右下角区域）：

于是我们可以把表示右下角的这块矩形（红色）的所有数 $+1$。然后查询一下能框住当前位置的所有矩形的右下角位置的值之和。就可以求到 $\sum_{j=1}^{i-1}F_{(x_i,y_i),(x_j,y_j)}$ 了。

同理，反过来从大到小枚举 $i$，就可以求 $\sum_{j=i+1}^{n^2}F_{(x_i,y_i),(x_j,y_j)}$ 了。

现在需要解决的问题是：在我们的操作中，出现了给子矩形 $+1$、求一个子矩形所有数的和。那么可以用二维树状数组（内存开销小一点，用二维线段树的话内存low不住）维护，既然一维树状数组可以区间加区间查询，那二维当然也可以，只是比较麻烦……

> Hint

其实不需要真的把 $i$ 从大到小、从小到大做两遍，可以一开始把二维树状数组的所有值赋为 $-(m^2-1)$。

意思是当前每个可以框住 $(x,y)$ 的矩形中，有 $(m^2-1)$ 个位置比 $(x,y)$ 大，然后因为 $(x,y)$ 和比它大的位置相减取绝对值后是 $-B_{x,y}$，所以乘上 $-1$。

然后每次从小到大枚举 $i$，每次把能框住 $(x_i,y_i)$ 的矩形右下角的位置 $+2$，其实是 $+1-(-1)$；即少了一个比 $(x,y)$ 大的数于是 $-(-1)$，多了一个比 $(x,y)$ 小的数于是 $+1$。

这样的话，每次查询能框住 $(x_i,y_i)$ 的矩形右下角的值之和就直接等于 $\sum_{j=1}^{i-1}F_{(x_i,y_i),(x_j,y_j)}-\sum_{j=i+1}^{n^2}F_{(x_i,y_i),(x_j,y_j)}$。

反正我代码里是这么写的 awa

# 源代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500,MOD=1e4+7;

struct NUMBER{
	int num;
	NUMBER(){}
	NUMBER(int x):num((x%MOD+MOD)%MOD){}
	NUMBER operator +(const NUMBER &B)const{
		int res=num+B.num;
		if(res>=MOD) res-=MOD;
		return res;
	}
	NUMBER operator -(const NUMBER &B)const{
		int res=num-B.num;
		if(res<0) res+=MOD;
		return res;
	}
	NUMBER operator *(const NUMBER &B)const{
		int res=num*B.num%MOD;
		if(res<0) res+=MOD;
		return res;
	}
	void operator +=(const NUMBER &B){
		(*this)=(*this)+B;
	}
};

struct NODE{int val,x,y;}nod[N*N+3];

int n,m;
NUMBER tre[N+3][N+3][4];

#define lowbit(x) (x&-x)
void Update(int x,int y,int v){
	NUMBER ad[4]={v,v*(x-1)%MOD,v*(y-1)%MOD,v*(x-1)%MOD*(y-1)%MOD};
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=n;j+=lowbit(j))
			for(int k=0;k<4;k++){
				tre[i][j][k]+=ad[k];
			}
}
void Query(int x,int y,NUMBER *res){
	for(int i=0;i<4;i++) res[i]=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j))
			for(int k=0;k<4;k++){
				res[k]+=tre[i][j][k];
			}
}
NUMBER extmp[4][4];
NUMBER QMatrix(int L,int R,int U,int D){ //查询矩形的元素之和
	Query(L-1,U-1,extmp[0]);
	Query(L-1,D,extmp[1]);
	Query(R,U-1,extmp[2]);
	Query(R,D,extmp[3]);
	for(int i=0;i<4;i++){
		extmp[3][i]=extmp[3][i]-extmp[2][i]-extmp[1][i]+extmp[0][i];
		extmp[2][i]=extmp[2][i]-extmp[0][i];
		extmp[1][i]=extmp[1][i]-extmp[0][i];
	}
	NUMBER Lx(R-L+1),Ly(D-U+1);
	NUMBER r(R),d(D);
	NUMBER ret=Lx*Ly*extmp[0][0]
		   +Lx*d*extmp[1][0] -Lx*extmp[1][2]
		   +Ly*r*extmp[2][0] -Ly*extmp[2][1]
		   +r*d*extmp[3][0] -d*extmp[3][1] -r*extmp[3][2] +extmp[3][3];
	return ret;
}
void UMatrix(int L,int R,int U,int D,int v){ //矩形所有元素+1
	Update(L,U,v);
	Update(R+1,D+1,v);
	Update(L,D+1,-v);
	Update(R+1,U,-v);
}

int Re(){
	int a=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
	return a;
}
bool cmp(NODE A,NODE B){return A.val<B.val;}
int main(){
//	freopen("input.txt","r",stdin);
	n=Re();m=Re();
	for(int i=1,tmp=0;i<=n;i++)
		for(int j=1;j<=n;j++){
			tmp++;
			nod[tmp].val=Re();
			nod[tmp].x=i;
			nod[tmp].y=j;
		}
	sort(nod+1,nod+1+n*n,cmp);
	UMatrix(1,n,1,n,((1-m*m)%MOD+MOD)%MOD);
	NUMBER ans(0);
	for(int i=1;i<=n*n;i++){
		int xi=nod[i].x,yi=nod[i].y;
		int L=max(m,xi),R=min(n,xi+m-1),
			U=max(m,yi),D=min(n,yi+m-1);
		NUMBER res=QMatrix(L,R,U,D);
//		printf("%d\n",res.num);
		ans+=res*nod[i].val;
		UMatrix(L,R,U,D,2);
	}
	printf("%d\n",(ans*2).num);
	return 0;
}

The End

Thanks for reading!

“烽烟乱世中怀抱勇气，慨然孤注手中棋” -《易水决》