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
|
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct
{
int type, x, y, z, rev, id;
node() {}
node(int type, int x, int y, int z, int rev, int id) :
type(type), x(x), y(y), z(z), rev(rev), id(id) {}
};
node st[400001], stack[400001], p[400001], b[400001];
int f[100001], tp = 0, c[400001];
int m, ans[100001];
void Add(int x, int d) { for (; x <= tp; x += (x & -x)) f[x] += d; }
int Sub(int x) { int ans = 0; for (; x; x -= (x & -x)) ans += f[x]; return ans; }
void dfs2(int l, int r)
{
if (l == r) return ;
int mid = (l + r) >> 1;
dfs2(l, mid), dfs2(mid + 1, r);
int tmpl = l, tmpr = mid + 1, tops = 0;
while (tmpl <= mid && tmpr <= r)
{
if (b[tmpl].y <= b[tmpr].y)
{
if (b[tmpl].type == 1) Add(b[tmpl].z, 1);
st[++ tops] = b[tmpl]; ++ tmpl;
}
else
{
if (b[tmpr].type == 2) ans[b[tmpr].id] += Sub(b[tmpr].z) * b[tmpr].rev;
st[++ tops] = b[tmpr]; ++ tmpr;
}
}
while (tmpl <= mid)
{
if (b[tmpl].type == 1) Add(b[tmpl].z, 1);
st[++ tops] = b[tmpl], ++ tmpl;
}
while (tmpr <= r)
{
if (b[tmpr].type == 2) ans[b[tmpr].id] += Sub(b[tmpr].z) * b[tmpr].rev;
st[++ tops] = b[tmpr]; ++ tmpr;
}
for (int i = l; i <= mid; i ++)
if (b[i].type == 1) Add(b[i].z, -1);
for (int i = l; i <= r; i ++)
b[i] = st[i - l + 1];
}
void dfs1(int l, int r)
{
if (l == r) return ;
int mid = (l + r) >> 1;
dfs1(l, mid), dfs1(mid + 1, r);
int N = 0, top = 0;
int tmpl = l, tmpr = mid + 1;
while (tmpl <= mid && tmpr <= r)
{
if (p[tmpl].x <= p[tmpr].x)
{
if (p[tmpl].type == 1) b[++ N] = p[tmpl];
stack[++ top] = p[tmpl]; ++ tmpl;
}
else
{
if (p[tmpr].type == 2) b[++ N] = p[tmpr];
stack[++ top] = p[tmpr]; ++ tmpr;
}
}
while (tmpl <= mid) stack[++ top] = p[tmpl], ++ tmpl;
while (tmpr <= r)
{
if (p[tmpr].type == 2) b[++ N] = p[tmpr];
stack[++ top] = p[tmpr]; ++ tmpr;
}
for (int i = l; i <= r; i ++)
p[i] = stack[i - l + 1];
if (N) dfs2(1, N);
}
int main( )
{
int T;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d", &T);
while (T --)
{
int type, x, y, z, tot = 0, id = 0;
int px, py, pz, qx, qy, qz;
tp = 0;
scanf("%d", &m);
for (int i = 1; i <= m; i ++)
{
scanf("%d", &type);
if (type == 1)
{
scanf("%d %d %d", &x, &y, &z);
p[++ tot] = node(1, x, y, z, 0, 0);
}
else
{
++ id;
scanf("%d %d %d %d %d %d", &px, &py, &pz, &qx, &qy, &qz);
p[++ tot] = node(2, qx, qy, qz, 1, id);
p[++ tot] = node(2, px - 1, qy, qz, -1, id);
p[++ tot] = node(2, qx, py - 1, qz, -1, id);
p[++ tot] = node(2, qx, qy, pz - 1, -1, id);
p[++ tot] = node(2, px - 1, py - 1, qz, 1, id);
p[++ tot] = node(2, px - 1, qy, pz - 1, 1, id);
p[++ tot] = node(2, qx, py - 1, pz - 1, 1, id);
p[++ tot] = node(2, px - 1, py - 1, pz - 1, -1, id);
}
}
for (int i = 1; i <= id; i ++) ans[i] = 0;
for (int i = 1; i <= tot; i ++)
c[++ tp] = p[i].z;
sort(c + 1, c + 1 + tp);
tp = unique(c + 1, c + 1 + tp) - c - 1;
for (int i = 1; i <= tp; i ++) f[i] = 0;
for (int i = 1; i <= tot; i ++)
p[i].z = lower_bound(c + 1, c + 1 + tp, p[i].z) - c;
dfs1(1, tot);
for (int i = 1; i <= id; i ++) printf("%dn", ans[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
|
近期评论