最开始写的代码里，每隔sqrt插入，rebuild一次。T2个点。

随后再自行随机数据后用vs的性能分析器发现，rebuild的开销过大。随后将每隔sqrt插入改为每隔$N^{0.7}$插入后过了。

个人的理解是插入不会出现极端的全部插入至一条链，同时查询也覆盖到这条链的情况，所以不用每隔sqrt次rebuild

这里的这只老年大学狗不能理解的地方是为什么，按道理来说，每隔sqrt rebuild一次复杂度应该是没问题的。T掉的原因是因为我的代码常数过大吗。 下附我的冗长的代码。~~~从K维的板子里改过来的，所以有很多很冗长的东西，加上这只辣鸡写代码本来就啰嗦QAQ，就有了这样难看的代码~~~

在线等一个神仙讲解复杂度QAQ

代码203行与204行标明了T与AC之间的区别

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<climits>
#include<cmath>
#include<map>
#include<set>
#include<deque>
#include<iomanip>
#include<bitset>

using namespace std;

struct Point
{
	int coord[2];
	int num = 0;
	int& operator [](const int& n) { return coord[n]; }
	const int& operator[](const int& n)const { return coord[n]; }
	Point operator=(const Point& p0)
	{
		coord[0] = p0[0];
		coord[1] = p0[1];
		num = p0.num;
		return *this;
	}
};

struct KD_tree
{
	int dimision = 2;

	vector<Point>tot_point;

	struct Space
	{
		int a[2] = { INT_MAX,INT_MAX }, b[2] = { 0,0 };

		bool operator<(const Space& space)const
		{
			for (int i = 0; i < 2; i++)
			{
				if (a[i] < space.a[i])
					return false;
				if (b[i] > space.b[i])
					return false;
			}
			return true;
		}

		bool operator!=(const Space& space)const
		{
			if (a[0] > space.b[0] || a[1] > space.b[1] || b[0] < space.a[0] || b[1] < space.a[1])
				return true;
			return false;
		}


		void divide(Space& s0, Space& s1, const int& dim, const int& val)const
		{
			s0 = s1 = *this;
			s0.b[dim] = s1.a[dim] = val;
		}
	};

	struct Inode
	{
		int dim, l, r;
		Space space;
		Space store;
		Point data;

		Inode() {}
		Inode(const int& _dim, const Space& _space, const Point& _data, const int& _l, const int& _r) :dim(_dim), space(_space), data(_data), l(_l), r(_r) {}
	};

	double calc_dis(const Point& p0, const Space& space)
	{
		double dis = 0;
		for (int dim = 0; dim < dimision; dim++)
		{
			if (space.a[dim] <= p0[dim] && p0[dim] <= space.b[dim])
				continue;
			dis += min(pow(space.a[dim] - p0[dim], 2), pow(space.b[dim] - p0[dim], 2));
		}
		return dis;
	}

	double calc_dis(const Point& p0, const Point& p1)
	{
		double dis = 0;
		for (int dim = 0; dim < dimision; dim++)
			dis += pow(p0[dim] - p1[dim], 2);
		return dis;
	}

	Inode* pool;
	int cnt = 0, root = 0;

	int build(const int& l, const int& r, const Space& space, vector<Point>& vec, int insert_cnt = -1)
	{
		if (r - l == 1)
		{
			pool[cnt++] = { -1,space,vec[l],-1,-1 };
			pool[cnt - 1].store.a[0] = pool[cnt - 1].store.b[0] = vec[l][0];
			pool[cnt - 1].store.a[1] = pool[cnt - 1].store.b[1] = vec[l][1];
			return cnt - 1;
		}

		int m = (l + r) >> 1;
		int sel_dim = 0;
		double sel_variance = 0;
		for (int dim = 0; dim < dimision; dim++)
		{
			double aver = 0, variance = 0;
			for (int i = l; i < r; i++)
				aver += vec[i][dim];
			aver /= (r - l + 1);
			for (int i = l; i < r; i++)
				variance += pow(vec[i][dim] - aver, 2);
			if (variance > sel_variance)
			{
				sel_dim = dim;
				sel_variance = variance;
			}
		}

		auto cmp = [&](const Point& p0, const Point& p1)
		{
			return p0[sel_dim] < p1[sel_dim];
		};

		nth_element(vec.begin() + l, vec.begin() + m, vec.begin() + r, cmp);

		Space s0, s1;
		space.divide(s0, s1, sel_dim, vec[m][sel_dim]);

		int ln = -1, rn = -1, now_cnt;
		if (insert_cnt == -1)
			now_cnt = cnt++;
		else
			now_cnt = insert_cnt;
		ln = build(l, m, s0, vec);
		rn = build(m, r, s1, vec);
		pool[now_cnt] = { sel_dim,space,vec[m],ln,rn };
		pool[now_cnt].data.num = pool[ln].data.num + pool[rn].data.num;
		for (int i = l; i < r; i++)
		{
			pool[now_cnt].store.a[0] = min(pool[now_cnt].store.a[0], vec[i].coord[0]);
			pool[now_cnt].store.a[1] = min(pool[now_cnt].store.a[1], vec[i].coord[1]);
			pool[now_cnt].store.b[0] = max(pool[now_cnt].store.b[0], vec[i].coord[0]);
			pool[now_cnt].store.b[1] = max(pool[now_cnt].store.b[1], vec[i].coord[1]);
		}
		return now_cnt;
	}

	int query(const int& num, const Space& space)
	{
		int ans = 0;
		const auto& n = pool[num];
		const auto& dim = n.dim;
		if (n.store < space)
			return n.data.num;
		if (n.l == -1 && n.r == -1)
		{
			for (int dim = 0; dim < dimision; dim++)
			{
				if (space.a[dim] > n.data[dim] || space.b[dim] < n.data[dim])
					return 0;
			}
			return n.data.num;
		}
		if (!(space != pool[n.l].store))
			ans += query(n.l, space);
		if (!(space != pool[n.r].store))
			ans += query(n.r, space);
		return ans;
	}

	void rebuild()
	{
		Space space = pool[root].space;
		cnt = 0;
		build(0, tot_point.size(), space, tot_point);
	}

	void insert(const Point& p0, const int& num, const int& t)
	{
		static int insert_cnt = 0;
		auto& n = pool[num];
		const auto& dim = n.dim;
		if (n.l == -1 && n.r == -1)
		{
			vector<Point>vec;
			vec.push_back(pool[num].data);
			vec.push_back(p0);
			build(0, 2, n.space, vec, num);
			tot_point.push_back(p0);
			//if (++insert_cnt > sqrt(tot_point.size()))
			if (++insert_cnt > pow(tot_point.size(), 0.7))
			{
				rebuild();
				insert_cnt = 0;
			}
			return;
		}
		n.data.num += t;
		n.store.a[0] = min(n.store.a[0], p0[0]);
		n.store.a[1] = min(n.store.a[1], p0[1]);
		n.store.b[0] = max(n.store.b[0], p0[0]);
		n.store.b[1] = max(n.store.b[1], p0[1]);
		if (p0[dim] < n.data[dim])
			insert(p0, n.l, t);
		else
			insert(p0, n.r, t);
	}

	KD_tree(vector<Point>vec, const int& point_num, Space& space)
	{
		dimision = 2;
		tot_point.assign(vec.begin(), vec.end());
		pool = new Inode[2 * 100000];
		build(0, vec.size(), space, vec);
	}

	~KD_tree() { delete[] pool; }
};

int main()
{
	ios_base::sync_with_stdio(false);

	int last_ans = 0, N;
	cin >> N;
	vector<Point>vec;
	Point p0, p1;
	p0.coord[0] = p0.coord[1] = 0;
	p1.coord[0] = p1.coord[1] = 500000;


	vec.push_back(p0);
	vec.push_back(p1);
	KD_tree::Space space;
	space.a[0] = p0.coord[0];
	space.a[1] = p0.coord[1];
	space.b[0] = p1.coord[0];
	space.b[1] = p1.coord[1];
	KD_tree kd_tree(vec, N, space);
	while (true)
	{
		int num;
		cin >> num;
		if (num == 3)
			break;
		switch (num)
		{
		default:
			break;
		case 1:
		{
			int x, y, t;
			cin >> x >> y >> t;
			x ^= last_ans;
			y ^= last_ans;
			t ^= last_ans;
			Point p;
			p.coord[0] = x;
			p.coord[1] = y;
			p.num = t;
			kd_tree.insert(p, num, t);
			break;
		}
		case 2:
		{
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			x1 ^= last_ans;
			x2 ^= last_ans;
			y1 ^= last_ans;
			y2 ^= last_ans;
			KD_tree::Space space;
			space.a[0] = x1;
			space.a[1] = y1;
			space.b[0] = x2;
			space.b[1] = y2;
			int ans = kd_tree.query(0, space);
			last_ans = ans;
			cout << ans << "\n";
		}
		}
	}
}