COGS 1752 [BOI2007] 摩基亚Mokia

【题目描述】#

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。

在定位系统中，世界被认为是一个W×W的正方形区域，由1×1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形，就有1<=x<=4,1<=y<=4（如图）: 请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。

【输入格式】#

有三种命令，意义如下：

命令	参数	意义
0	W	初始化一个全零矩阵。本命令仅开始时出现一次。
1	x y A	向方格(x,y)中添加A个用户。A是正整数。
2	X1 Y1 X2 Y2	查询X1<=x<=X2，Y1<=y<=Y2所规定的矩形中的用户数量
3	无参数	结束程序。本命令仅结束时出现一次。

【输出格式】#

对所有命令2，输出一个一行整数，即当前询问矩形内的用户数量。

【输入样例】#

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

【输出样例】#

3
5

【提示】#

输入	输出	意义
0 4		大小为4×4的全零正方形
1 2 3 3		向(2,3)方格加入3名用户
2 1 1 3 3		查询矩形1<=x<=3,1<=y<=3内的用户数量
	3	查询结果
1 2 2 2		向(2,2)方格加入2名用户
2 2 2 3 4		查询矩形2<=x<=3,2<=y<=4内的用户数量
	5	查询结果
3		终止程序

【数据规模】

1<=W<=2000000
1<=X1<=X2<=W
1<=Y1<=Y2<=W
1<=x,y<=W
0<A<=10000
命令1不超过160000个。
命令2不超过10000个。

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