BZOJ 2639: 矩形计算(二维莫队)

Description

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

Input

  第一行两个整数n,m表示矩阵的规模。
接下来n行每行m个整数,表示这个矩阵的每个元素。
再下来一行一个整数q,表示询问个数。
接下来q行每行四个正整数x1,y1,x2,y2,询问以第x1行第y1列和第x2行第y2列的连线为对角线的子矩阵的权值。

Output

  输出q行每行一个整数回答对应询问。

Sample Input

3 4
1 3 2 1
1 3 2 4
1 2 3 4
8
1 2 2 1
1 1 2 1
1 1 3 4
1 1 1 1
2 2 3 3
3 4 2 2
1 3 3 1
2 4 3 4

Sample Output

8
4
38
1
8
12
27
4

HINT

对于全部数据

1<=n,m<=200

q<=100000

|矩阵元素大小|<=2*109

Source

Solution

今天NOIPlus灰心赛T2

n眼莫队,然而并不会证复杂度,百度一搜矩形莫队就搜出了原题。。

考虑对左上的端点的编号分块排序,右下按编号排序(编号从左到右,从上到下)

注意指针移动时要维护好两个指针对的关系,可以通过每个指针都移动一次保证关系不改变

 

0 0 vote
Article Rating
Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
hh
hh
1 月 之前

?

111
111
1 月 之前
Reply to  hh

?