\(\text{Problem}\)
标准四维偏序
带修改(加和删除)和询问的三维空间正方体内部(包括边上)的点的数目
\(\text{Analysis}\)
打法很多,\(\text{cdq}\) 套 \(\text{cdq}\) 加上树状数组处理或者 \(\text{cdq}\) 套树套树(如树状数组套线段树)等方法都可以
\(\text{K-D tree}\) 的 \(O(n^{1.75})\) 看起来不怎行,但可以过
当然是在开 \(O\) 的情况下
个人选择了 \(\text{cdq}\) 套树状数组套线段树(离散化节省空间)
\(\text{Code}\)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
int n, m, ans[N * 2], tot, top, My, Mz, bz[N * 2];
inline void read(int &x)
{
x = 0; char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();
}
struct node{
int ty, x, y, z, v, id;
}Q[N * 2], st[N], Q1[N * 2];
int Y[N * 2], Z[N * 2];
inline void lisan()
{
for(register int i = 1; i <= tot; i++)
{
Y[++Y[0]] = Q[i].y;
if (!Q[i].ty) Y[++Y[0]] = Q[i].y - Q[i].v - 1;
}
sort(Y + 1, Y + Y[0] + 1);
My = unique(Y + 1, Y + Y[0] + 1) - Y - 1;
for(register int i = 1; i <= tot; i++)
{
Z[++Z[0]] = Q[i].z;
if (!Q[i].ty) Z[++Z[0]] = Q[i].z - Q[i].v;
}
sort(Z + 1, Z + Z[0] + 1);
Mz = unique(Z + 1, Z + Z[0] + 1) - Z - 1;
}
inline int findY(int y)
{
int l = 1, r = My, mid, ret = 1;
while (l <= r)
{
mid = (l + r) >> 1;
if (Y[mid] <= y) ret = mid, l = mid + 1;
else r = mid - 1;
}
return ret;
}
inline int findZ(int z)
{
int l = 1, r = Mz, mid, ret = 1;
while (l <= r)
{
mid = (l + r) >> 1;
if (Z[mid] <= z) ret = mid, l = mid + 1;
else r = mid - 1;
}
return ret;
}
struct SegTree{
int rt[N * 2], ls[N * 289], rs[N * 289], sum[N * 289], size;
void update_D2(int &p, int l, int r, int z, int v)
{
if (!p) p = ++size, ls[p] = rs[p] = sum[p] = 0;
sum[p] += v;
if (l == r) return;
int mid = (l + r) >> 1;
if (z <= mid) update_D2(ls[p], l, mid, z, v);
else update_D2(rs[p], mid + 1, r, z, v);
}
int query_D2(int p, int l, int r, int z0, int z1)
{
if (!p) return 0;
if (z0 <= l && r <= z1) return sum[p];
int mid = (l + r) >> 1, res = 0;
if (z0 <= mid) res = query_D2(ls[p], l, mid, z0, z1);
if (z1 > mid) res += query_D2(rs[p], mid + 1, r, z0, z1);
return res;
}
}ST;
struct BIT{
inline int lowbit(int x){return x & (-x);}
inline void clear(int y){for(int i = findY(y); i <= My && ST.rt[i]; i += lowbit(i)) ST.rt[i] = 0;}
inline void update_D1(int y, int z, int v)
{
if (!y) return;
y = findY(y), z = findZ(z);
for(register int i = y; i <= My; i += lowbit(i)) ST.update_D2(ST.rt[i], 1, Mz, z, v);
}
inline int query(int y0, int y1, int z0, int z1)
{
y0 = findY(y0 - 1), y1 = findY(y1), z0 = findZ(z0), z1 = findZ(z1);
return query_D1(y1, z0, z1) - query_D1(y0, z0, z1);
}
inline int query_D1(int y, int z0, int z1)
{
if (!y) return 0;
int res = 0;
for(register int i = y; i; i -= lowbit(i)) res += ST.query_D2(ST.rt[i], 1, Mz, z0, z1);
return res;
}
}T;
void cdq(int l, int r)
{
if (l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
int i = l, j = mid + 1, k = l - 1;
while (i <= mid && j <= r)
if (Q[i].x <= Q[j].x)
{
if (Q[i].ty) T.update_D1(Q[i].y, Q[i].z, Q[i].v);
Q1[++k] = Q[i++];
}
else{
if (!Q[j].ty)
bz[Q[j].id] = 1, ans[Q[j].id] += T.query(Q[j].y - Q[j].v, Q[j].y, Q[j].z - Q[j].v, Q[j].z);
Q1[++k] = Q[j++];
}
while (i <= mid)
{
if (Q[i].ty) T.update_D1(Q[i].y, Q[i].z, Q[i].v);
Q1[++k] = Q[i++];
}
while (j <= r)
{
if (!Q[j].ty)
bz[Q[j].id] = 1, ans[Q[j].id] += T.query(Q[j].y - Q[j].v, Q[j].y, Q[j].z - Q[j].v, Q[j].z);
Q1[++k] = Q[j++];
}
for(i = l; i <= mid; i++)
if (Q[i].ty && Q[i].y) T.clear(Q[i].y);
ST.size = 0;
for(i = l; i <= r; i++) Q[i] = Q1[i];
}
int main()
{
read(n);
for(int i = 1, x, y, z; i <= n; i++) read(x), read(y), read(z), Q[++tot] = node{1, ++x, ++y, ++z, 1};
read(m);
char op[10];
for(int i = 1, x, y, z, v; i <= m; i++)
{
scanf("%s", op);
if (op[0] == 'A') read(x), read(y), read(z), Q[++tot] = node{1, ++x, ++y, ++z, 1}, st[++top] = Q[tot];
else if (op[0] == 'Q') read(x), read(y), read(z), read(v), x = x + 1 + v, y = y + 1 + v, z = z + 1 + v,
Q[++tot] = node{0, x, y, z, v, i}, Q[++tot] = node{0, x - v - 1, y, z, v, i + m};
else Q[++tot] = st[top--], Q[tot].v = -1;
}
lisan();
cdq(1, tot);
for(int i = 1; i <= m; i++)
if (bz[i]) printf("%d\n", ans[i] - ans[i + m]);
}