1. 题目

传送门=￣ω￣=

2. 题解

我有一个特别好的毒舌句来吐槽出题人，可惜这里空间太小了我写不下

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

其实 BZOJ 上的也还好，只卡空间

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;
}