NekoMio's Blog

美しいものが起こることを常に信じている

Description

维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):
“1 x y a”
“2 x1 y1 x2 y2”
“3”
输入1:你需要把(x,y)(第x行第y列)的格子权值增加a
输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出
输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 800005;
struct Query
{
int x, y, op, val, id, pos;
bool operator < (const Query &a) const
{
return x == a.x ? op < a.op : x < a.x;
}
} Ask[MAXN], tmp[MAXN];
int n, m, Ans[MAXN];
#define lowbit(_) ((_)&(-_))
struct BIT
{
int Sum[2000005];
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
Sum[i] += c;
}
int Query(int x)
{
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i))
ans += Sum[i];
return ans;
}
}bit;
void add()
{
int x1, y1, x2, y2;
scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
++Ans[0];
Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y1 - 1, Ask[m].val = 1, Ask[m].op = 1;
Ask[++m].pos = Ans[0], Ask[m].x = x2 , Ask[m].y = y2 , Ask[m].val = 1, Ask[m].op = 1;
Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y2 , Ask[m].val =-1, Ask[m].op = 1;
Ask[++m].pos = Ans[0], Ask[m].x = x2 , Ask[m].y = y1 - 1, Ask[m].val =-1, Ask[m].op = 1;
}
void CDQ(int l, int r)
{
if (l == r)
return;
int mid = l + r >> 1, l1 = l, l2 = mid + 1;
for (int i = l; i <= r; i++)
{
if (Ask[i].id <= mid && !Ask[i].op)
bit.add(Ask[i].y, Ask[i].val);
if (Ask[i].id > mid && Ask[i].op)
Ans[Ask[i].pos] += Ask[i].val * bit.Query(Ask[i].y);
}
for (int i = l; i <= r; i++)
if (Ask[i].id <= mid && !Ask[i].op)
bit.add(Ask[i].y, -Ask[i].val);
for (int i = l; i <= r; i++)
{
if (Ask[i].id <= mid)
tmp[l1++] = Ask[i];
else tmp[l2++] = Ask[i];
}
for (int i = l; i <= r; i++)
Ask[i] = tmp[i];
CDQ(l, mid);
CDQ(mid + 1, r);
return;
}
int main()
{
freopen("mokia.in", "r", stdin);
freopen("mokia.out", "w", stdout);
int op;
scanf ("%d%d", &op, &n);
while (1)
{
scanf ("%d", &op);
if (op == 1)
{
m++;
scanf ("%d%d%d", &Ask[m].x, &Ask[m].y, &Ask[m].val);
}
else if (op == 2)
add();
else break;
}
for (int i = 1; i <= m; i++)
Ask[i].id = i;
sort(Ask + 1, Ask + m + 1);
CDQ(1 ,m);
for (int i = 1; i <= Ans[0]; i++)
printf ("%d\n", Ans[i]);
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2017/10/21/115/

本文最后更新于 天前,文中所描述的信息可能已发生改变