BZOJ2639 矩形计算

发表于 | 更新于

题意

输入一个nm的矩阵，矩阵的每一个元素都是一个整数，然后有q个询问，每次询问一个子矩阵的权值。矩阵的权值是这样定义的，对于一个整数x，如果它在该矩阵中出现了p次，那么它给该矩阵的权值就贡献p2。

做法

题意描述是标准的莫队。但因为是矩阵，那就是二维莫队咯。 考虑一下，应该让块紧凑一些，转移复杂度会比较小，因此这个的分块就相当于横切几刀竖切几刀分成的块。 类比序列的莫队，(i,j)(i,j)位置所在的块为([i−1n]+1−1)m+[j−1m]+1([\frac {i-1}{\sqrt n}]+1-1)\sqrt m+[\frac {j-1}{\sqrt m}]+1 转移的时候也很简单，类比序列先扩再缩就行了。

CODE

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <utility>
#define red(x) scanf("%d",&x)
const int MAXN=200+1;
const int MAXQ=100000+1;
inline int sqr(const int& x)
{
	return x*x;
}
int rf[MAXN][MAXN],v[MAXN][MAXN],lis[MAXN*MAXN],bn[MAXN][MAXN],ANS[MAXQ];
struct Query
{
	int id,x1,y1,x2,y2;
	bool operator <(const Query& a) const
	{
		if(bn[x1][y1]!=bn[a.x1][a.y1])
			return bn[x1][y1]<bn[a.x1][a.y1];
		return rf[x2][y2]<rf[a.x2][a.y2];
	}
}q[MAXQ];int qc;
int cnt[MAXN*MAXN],ans;
inline void mod(int x,int y,int d)
{
	ans-=sqr(cnt[v[x][y]]);
	cnt[v[x][y]]+=d;
	ans+=sqr(cnt[v[x][y]]);
}
inline void ModifyX(int x,int b,int t,int d)
{
	for(int i=t;i<=b;i++)
		mod(x,i,d);
}
inline void ModifyY(int y,int l,int r,int d)
{
	for(int i=l;i<=r;i++)
		mod(i,y,d);
}
void Mo()
{
	int x1=1,x2=1,y1=1,y2=1;
	cnt[v[1][1]]=1;
	ans=1;
	for(int i=1;i<=qc;i++)
	{
		while(x1>q[i].x1)
			ModifyX(--x1,y2,y1,1);
		while(x2<q[i].x2)
			ModifyX(++x2,y2,y1,1);
		while(y1>q[i].y1)
			ModifyY(--y1,x1,x2,1);
		while(y2<q[i].y2)
			ModifyY(++y2,x1,x2,1);

		while(x1<q[i].x1)
			ModifyX(x1++,y2,y1,-1);
		while(x2>q[i].x2)
			ModifyX(x2--,y2,y1,-1);
		while(y1<q[i].y1)
			ModifyY(y1++,x1,x2,-1);
		while(y2>q[i].y2)
			ModifyY(y2--,x1,x2,-1);
		ANS[q[i].id]=ans;	
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int n,m,t1,t2,t3;red(n),red(m);
	int ns=sqrt(n),ms=sqrt(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			red(t1);
			lis[rf[i][j]=(i-1)*m+j]=v[i][j]=t1;
			bn[i][j]=(((i-1)/ns+1)-1)*ms+(j-1)/ms+1;
		}
	int lisc=m*n;
	std::sort(lis+1,lis+1+lisc);
	lisc=std::unique(lis+1,lis+1+lisc)-lis-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			v[i][j]=std::lower_bound(lis+1,lis+1+lisc,v[i][j])-lis;
	red(qc);
	for(int i=1;i<=qc;i++)
	{
		red(q[i].x1),red(q[i].y1),red(q[i].x2),red(q[i].y2);
		if(q[i].x1>q[i].x2)
			std::swap(q[i].x1,q[i].x2);
		if(q[i].y1>q[i].y2)
			std::swap(q[i].y1,q[i].y2);
		q[i].id=i;
	}
	std::sort(q+1,q+1+qc);
	Mo();
	for(int i=1;i<=qc;i++)
		printf("%d\n",ANS[i]);
	return 0;
}