除草

Posted on |

退役多年，连CDQ分治都不会写了。
BC#20 stars
单点修改，立方体内点数询问。
容斥以后直接上分治。
以时间那一维为基准，第一次分治x，第二次分治y，然后对点在z这一维进行树状数组统计。
复杂度为$O(nlog^3n)$。

stars.cpp
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 <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct node
{
	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("%d\n", ans[i]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}