Blackops

初心易得，始终难守

0%

BZOJ 4066 简单题（KD-tree维护多维区间）

发表于 分类于 ， ，

4066: 简单题

Time Limit: 50 Sec Memory Limit: 20 MB
Submit: 3422 Solved: 891
[Submit][Status][Discuss]
Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令
参数限制
内容
1 x y A
1<=x,y<=N，A是正整数
将格子x,y里的数字加上A
2 x1 y1 x2 y2
1<=x1<= x2<=N
1<=y1<= y2<=N
输出x1 y1 x2 y2这个矩形内的数字和
3
无
终止程序
Input

输入文件第一行一个正整数N。
接下来每行一个操作。每条命令除第一个数字之外，
均要异或上一次输出的答案last_ans，初始时last_ans=0。
Output

对于每个2操作，输出一个对应的答案。
Sample Input

4

1 2 3 3

2 1 1 3 3

1 1 1 1

2 1 1 0 7

3
Sample Output

3

5
HINT

数据规模和约定

$1<=N<=500000$,操作数不超过$200000$个，内存限制$20M$，保证答案在int范围内并且解码之后数据仍合法。

样例解释见OJ2683

新加数据一组，但未重测——2015.05.24

题目链接：BZOJ 4066
早上开始写的题目，结果把$n$错看成数据组数，用while (n—)来做，一直WA在8000多毫秒处。。最后发现$n$是棋盘大小。。。。
这题用$KD-tree$维护高维的区间询问和修改情况，据说单次查询和插入复杂度据说是$O(\sqrt N)$，然后写完发现这不还是个普通$BST$吗，编程复杂度比$treap$简单一些，但是要注意的是$pushup$的时候不能简单地$T[k].sum+=T[son].sum$，因为节点信息维护要用儿子加当前节点来算，即完全重新计算，而不是简单地用$+=$来解决，不然每一次$pushup$的时候早就出错了，然后这题由于点太多，可能导致形态太差，比如“一条链”的情况，因此要把每次插入的点记录下来，每次加入的点超过设定的点树就用这些点重新$build$一棵树即可，过程中注意先清空节点原来的信息；
查询的时候稍微剪枝一下，比如当前点管理的区域完全在查询区域内，那就直接返回$T[cur].sum$就好了，如果要查询的点管辖的区域跟查询区域完全没交集，那就不用往下查了，跟线段树有一些类似，反正越写越感觉像$treap$。。。。
代码：

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200010;
int idx;
struct KD
{
    int ls, rs;
    int d[2], mn[2], mx[2];
    int v, sum;
    void init()
    {
        ls = rs = 0;
        v = sum = 0;
    }
} T[N];
struct info
{
    int d[2], v;
    bool operator<(const info &rhs)const
    {
        return d[idx] < rhs.d[idx];
    }
} arr[N];
int rt, sz;
int _x1, _y1, _x2, _y2;

void init()
{
    rt = sz = 0;
}
inline void pushup(int k)
{
    int l = T[k].ls, r = T[k].rs;
    T[k].sum = T[k].v;
    if (l)
    {
        for (int i = 0; i < 2; ++i)
        {
            T[k].mn[i] = min(T[k].mn[i], T[l].mn[i]);
            T[k].mx[i] = max(T[k].mx[i], T[l].mx[i]);
        }
        T[k].sum += T[l].sum;
    }
    if (r)
    {
        for (int i = 0; i < 2; ++i)
        {
            T[k].mn[i] = min(T[k].mn[i], T[r].mn[i]);
            T[k].mx[i] = max(T[k].mx[i], T[r].mx[i]);
        }
        T[k].sum += T[r].sum;
    }
}
void ins(int &k, int d[], int v, int dim)
{
    if (!k)
    {
        k = ++sz;
        for (int i = 0; i < 2; ++i)
            T[k].d[i] = T[k].mn[i] = T[k].mx[i] = d[i];
        T[k].ls = T[k].rs = 0;
        T[k].v = v;
        T[k].sum = v;
    }
    else
    {
        if (T[k].d[0] == d[0] && T[k].d[1] == d[1])
        {
            T[k].v += v;
            T[k].sum += v;
        }
        else
        {
            if (d[dim] <= T[k].d[dim])
                ins(T[k].ls, d, v, dim ^ 1);
            else
                ins(T[k].rs, d, v, dim ^ 1);
            pushup(k);
        }
    }
}
inline int inMat(int x, int y, int xx, int yy)
{
    return _x1 <= x && xx <= _x2 && _y1 <= y && yy <= _y2;
}
inline int outMat(int x, int y, int xx, int yy)
{
    return _x2 < x || xx < _x1 || _y2 < y || yy < _y1;
}
int query(int k)
{
    if (inMat(T[k].mn[0], T[k].mn[1], T[k].mx[0], T[k].mx[1]))
        return T[k].sum;
    else
    {
        int ret = 0;
        if (inMat(T[k].d[0], T[k].d[1], T[k].d[0], T[k].d[1]))
            ret += T[k].v;
        int l = T[k].ls, r = T[k].rs;
        if (l && !outMat(T[l].mn[0], T[l].mn[1], T[l].mx[0], T[l].mx[1]))
            ret += query(l);
        if (r && !outMat(T[r].mn[0], T[r].mn[1], T[r].mx[0], T[r].mx[1]))
            ret += query(r);
        return ret;
    }
}
void build(int &k, int l, int r, int dim)
{
    k = ++sz;
    idx = dim;
    int mid = MID(l, r);
    nth_element(arr + l, arr + mid, arr + r + 1);
    T[k].init();
    for (int i = 0; i < 2; ++i)
        T[k].mn[i] = T[k].mx[i] = T[k].d[i] = arr[mid].d[i];
    T[k].sum = T[k].v = arr[mid].v;
    T[k].ls = T[k].rs = 0;
    if (l < mid)
        build(T[k].ls, l, mid - 1, dim ^ 1);
    if (mid < r)
        build(T[k].rs, mid + 1, r, dim ^ 1);
    pushup(k);
}
int main(void)
{
    init();
    int n, ops;
    int cnt = 0, flag = 0, ans = 0;
    scanf("%d", &n);
    while (~scanf("%d", &ops) && ops != 3)
    {
        if (ops == 1)
        {
            int d[2], v;
            scanf("%d%d%d", &d[0], &d[1], &v);
            d[0] ^= ans;
            d[1] ^= ans;
            v ^= ans;
            ins(rt, d, v, 0);
            ++cnt, ++flag;
            arr[cnt].d[0] = d[0];
            arr[cnt].d[1] = d[1];
            arr[cnt].v = v;
            if (flag >= 10000)
            {
                init();
                build(rt, 1, cnt, 0);
                flag = 0;
            }
        }
        else
        {
            scanf("%d%d%d%d", &_x1, &_y1, &_x2, &_y2);
            _x1 ^= ans;
            _y1 ^= ans;
            _x2 ^= ans;
            _y2 ^= ans;
            printf("%d\n", ans = query(rt));
        }
    }
    return 0;
}