题解：CF2044H Hard Demon Problem
将行和列分开考虑。
在每组询问 $(x_1,y_1,x_2,y_2)$ 中：
不难想到对行和列分别做 $i \times a_{i,j}$ 和 $j \times a_{i,j}$ 的前缀和处理。由于列的下标之差不为 $1$，所以需要先对其做扩大倍数的处理后再将其相加。设最终要求的 $\sum i a_i$ 的 $i$ 为系数，那么对于一组询问，可以得到以下系数矩阵：
然而正确的系数矩阵应为：
将矩阵中的每一个数字都减去 $x_1(y_2 - y_1 + 1) + y_1 - 1$ 次即可，也就是再维护一个普通的二维前缀和后处理。总时间复杂度为 $O(t(n^2 + q))$，代码如下：
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,q;
ll sum[MAX][MAX],sumx[MAX][MAX],sumy[MAX][MAX];
int main ()
{
t = read ();
while (t--)
{
n = read ();q = read ();
for (int i = 1;i <= n;++i)
{
for (int j = 1;j <= n;++j)
{
int x = read ();
sum[i][j] = x + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
sumx[i][j] = i * x + sumx[i - 1][j] + sumx[i][j - 1] - sumx[i - 1][j - 1];
sumy[i][j] = j * x + sumy[i - 1][j] + sumy[i][j - 1] - sumy[i - 1][j - 1];;
}
}
while (q--)
{
int sx = read (),sy = read (),fx = read (),fy = read ();
ll s = sum[fx][fy] - sum[sx - 1][fy] - sum[fx][sy - 1] + sum[sx - 1][sy - 1];
ll sum_x = sumx[fx][fy] - sumx[sx - 1][fy] - sumx[fx][sy - 1] + sumx[sx - 1][sy - 1];
ll sum_y = sumy[fx][fy] - sumy[sx - 1][fy] - sumy[fx][sy - 1] + sumy[sx - 1][sy - 1];
printf ("%lld ",sum_x * (fy - sy + 1) + sum_y - s * (1ll * sx * (fy - sy + 1) + sy - 1));
}
puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
