# 2. 题解

## 你××出个数据结构题还卡常？你是不是脑子进×了？

luogu 上的我真的已经无力吐槽。2S 你这是在搞笑吗？我常数稍微大了个 $0.2333333$倍就 TM60 分。。。

#include <bits/stdc++.h>

#define NS (200005)
#define DS (2)
#define ALP (0.75)

using namespace std;

template <typename _Tp>void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, root, sz, D, opt, ans;

stack<int> rub;

struct N
{
int d[DS], v, mx[DS], mn[DS], l, r, sz, sum;
int& operator [] (const int a){return d[a];}
bool operator < (N another) const {return d[D] < another[D];}
}arr[NS], e[NS], t;

struct M{int mn[2], mx[2];}q;

int MKN()
{
if (rub.empty()) return ++sz;
int tmp = rub.top();
memset(&e[tmp], 0, sizeof(N)), rub.pop();
return tmp;
}

void pup(int a)
{
int l = e[a].l, r = e[a].r;
e[a].sum = e[a].v + e[l].sum + e[r].sum;
e[a].sz = e[l].sz + e[r].sz + 1;
for (int i = 0; i < DS; i++)
{
e[a].mx[i] = e[a].mn[i] = e[a][i];
if (l)
{
e[a].mx[i] = max(e[a].mx[i], e[l].mx[i]);
e[a].mn[i] = min(e[a].mn[i], e[l].mn[i]);
}
if (r)
{
e[a].mx[i] = max(e[a].mx[i], e[r].mx[i]);
e[a].mn[i] = min(e[a].mn[i], e[r].mn[i]);
}
}
}
void rec(int a, int tot = 0)
{
if (!a) return;
rec(e[a].l, tot), tot += e[e[a].l].sz + 1;
arr[tot] = e[a], rub.push(a);
rec(e[a].r, tot);
}

int Build(int l, int r, int d = 0)
{
if (l > r) return 0;
D = d;
int a = MKN(), mid = (l + r) >> 1;
nth_element(arr + l, arr + mid, arr + r + 1);
e[a] = arr[mid];
e[a].l = Build(l, mid - 1, d ^ 1);
e[a].r = Build(mid + 1, r, d ^ 1);
pup(a); return a;
}

void check(int& a, int d)
{
if (e[a].sz * ALP < e[e[a].l].sz || e[a].sz * ALP < e[e[a].r].sz)
rec(a), a = Build(1, e[a].sz, d);
}

void insert(int& a = root, int d = 0)
{
if (!a){a = MKN(), e[a] = t, pup(a); return;}
if (t[d] < e[a][d]) insert(e[a].l, d ^ 1);
else insert(e[a].r, d ^ 1);
pup(a), check(a, d);
}

bool jud1(int a)
{
return q.mn[0] <= e[a].mn[0] && e[a].mx[0] <= q.mx[0] &&
q.mn[1] <= e[a].mn[1] && e[a].mx[1] <= q.mx[1];
}

bool jud2(int a)
{
return q.mn[0] > e[a].mx[0] || e[a].mn[0] > q.mx[0] ||
q.mn[1] > e[a].mx[1] || e[a].mn[1] > q.mx[1];
}

bool jud3(int a)
{
return q.mn[0] <= e[a][0] && e[a][0] <= q.mx[0] &&
q.mn[1] <= e[a][1] && e[a][1] <= q.mx[1];
return 1;
}

void query(int a = root)
{
if (!a) return;
if (jud1(a)) {ans += e[a].sum; return;}
if (jud2(a)) return;
if (jud3(a)) ans += e[a].v;
query(e[a].l), query(e[a].r);
}

int main (int argc, char const* argv[])
{
IN(n);
int a, b, c, d;
while (IN(opt), opt != 3)
if (opt == 1)
{
IN(a), IN(b), IN(c);
a ^= ans, b ^= ans, c ^= ans;
t[0] = a, t[1] = b, t.v = c, insert();
}
else
{
IN(a), IN(b), IN(c), IN(d);
a ^= ans, b ^= ans, c ^= ans, d ^= ans;
ans = 0, q.mn[0] = a, q.mn[1] = b, q.mx[0] = c, q.mx[1] = d;
query(), printf("%d\n", ans);
}
return 0;
}