BZOJ 1176 [Balkan2007]Mokia CDQ

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#

Sample Output#

Code#

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int MAXN = 800005;
6
struct Query
7
{
8
    int x, y, op, val, id, pos;
9
    bool operator < (const Query &a) const
10
    {
11
        return x == a.x ? op < a.op : x < a.x;
12
    }
13
} Ask[MAXN], tmp[MAXN];
14
int n, m, Ans[MAXN];
15
#define lowbit(_) ((_)&(-_))
16
struct BIT
17
{
18
    int Sum[2000005];
19
    void add(int x, int c)
20
    {
21
        for (int i = x; i <= n; i += lowbit(i))
22
            Sum[i] += c;
23
    }
24
    int Query(int x)
25
    {
26
        int ans = 0;
27
        for (int i = x; i > 0; i -= lowbit(i))
28
            ans += Sum[i];
29
        return ans;
30
    }
31
}bit;
32
void add()
33
{
34
    int x1, y1, x2, y2;
35
    scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
36
    ++Ans[0];
37
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y1 - 1, Ask[m].val = 1, Ask[m].op = 1;
38
    Ask[++m].pos = Ans[0], Ask[m].x = x2    , Ask[m].y = y2    , Ask[m].val = 1, Ask[m].op = 1;
39
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y2    , Ask[m].val =-1, Ask[m].op = 1;
40
    Ask[++m].pos = Ans[0], Ask[m].x = x2    , Ask[m].y = y1 - 1, Ask[m].val =-1, Ask[m].op = 1;
41
}
42
void CDQ(int l, int r)
43
{
44
    if (l == r)
45
        return;
46
    int mid = l + r >> 1, l1 = l, l2 = mid + 1;
47
    for (int i = l; i <= r; i++)
48
    {
49
        if (Ask[i].id <= mid && !Ask[i].op)
50
            bit.add(Ask[i].y, Ask[i].val);
51
        if (Ask[i].id > mid && Ask[i].op)
52
            Ans[Ask[i].pos] += Ask[i].val * bit.Query(Ask[i].y);
53
    }
54
    for (int i = l; i <= r; i++)
55
        if (Ask[i].id <= mid && !Ask[i].op)
56
            bit.add(Ask[i].y, -Ask[i].val);
57
    for (int i = l; i <= r; i++)
58
    {
59
        if (Ask[i].id <= mid)
60
            tmp[l1++] = Ask[i];
61
        else tmp[l2++] = Ask[i];
62
    }
63
    for (int i = l; i <= r; i++)
64
        Ask[i] = tmp[i];
65
    CDQ(l, mid);
66
    CDQ(mid + 1, r);
67
    return;
68
}
69
int main()
70
{
71
    freopen("mokia.in", "r", stdin);
72
    freopen("mokia.out", "w", stdout);
73
    int op;
74
    scanf ("%d%d", &op, &n);
75
    while (1)
76
    {
77
        scanf ("%d", &op);
78
        if (op == 1)
79
        {
80
            m++;
81
            scanf ("%d%d%d", &Ask[m].x, &Ask[m].y, &Ask[m].val);
82
        }
83
        else if (op == 2)
84
            add();
85
        else break;
86
    }
87
    for (int i = 1; i <= m; i++)
88
        Ask[i].id = i;
89
    sort(Ask + 1, Ask + m + 1);
90
    CDQ(1 ,m);
91
    for (int i = 1; i <= Ans[0]; i++)
92
        printf ("%d\n", Ans[i]);
93
}