记录编号	593160	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	5.536 s
提交时间	2024-08-23 21:27:50	内存使用	6.19 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 2e5+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}
void kmin(int &x,int y){x = min(x,y);}
void kmax(int &x,int y){x = max(x,y);}


int n,las;
struct made{int x[2],z;}a[N];
db w[2],av[2];
int cnt,B,la,rt; 
struct KDTree{
	struct dat{
		int ls,rs,val;
		int mi[2],mx[2];
	}s[N];	
	#define ls(p) s[p].ls
	#define rs(p) s[p].rs
	void pushup(int p){
		s[p].val = s[ls(p)].val + s[rs(p)].val + a[p].z;
		for(int i = 0;i < 2;i++){
			s[p].mi[i] = s[p].mx[i] = a[p].x[i];
			if(ls(p))kmin(s[p].mi[i],s[ls(p)].mi[i]),kmax(s[p].mx[i],s[ls(p)].mx[i]);
			if(rs(p))kmin(s[p].mi[i],s[rs(p)].mi[i]),kmax(s[p].mx[i],s[rs(p)].mx[i]);
		}
	}
	void build(int &p,int l,int r){
		if(l > r)return p = 0,void();
		w[0] = w[1] = av[0] = av[1] = 0;
		for(int i = l;i <= r;i++)
			for(int j = 0;j < 2;j++)av[j] += a[i].x[j];
		for(int j = 0;j < 2;j++)av[j] = av[j] / (r-l+1);
		for(int i = l;i <= r;i++)
			for(int j = 0;j < 2;j++)w[j] += (a[i].x[j] - av[j]) * (a[i].x[j] - av[j]);
		int mid = l + r >> 1,op = w[1] > w[0] ? 1 : 0;
		nth_element(a+l,a+mid,a+r+1,[&](made a,made b){return a.x[op] < b.x[op];});
		p = mid;
		build(ls(p),l,mid-1),build(rs(p),mid+1,r);
		pushup(p); 
	}
	int cal(int p,int l,int r,int L,int R){
		if(!p || s[p].mi[0] > r || s[p].mx[0] < l || s[p].mi[1] > R || s[p].mx[1] < L)return 0;
		if(l <= s[p].mi[0] && s[p].mx[0] <= r && L <= s[p].mi[1] && s[p].mx[1] <= R)return s[p].val;
		int res = 0;
		if(l <= a[p].x[0] && a[p].x[0] <= r && L <= a[p].x[1] && a[p].x[1] <= R)res = a[p].z;
		return res + cal(ls(p),l,r,L,R) + cal(rs(p),l,r,L,R);
	}
	int ask(int l,int r,int L,int R){
		int ans = 0;
		for(int i = la+1;i <= cnt;i++)
			if(l <= a[i].x[0] && a[i].x[0] <= r && L <= a[i].x[1] && a[i].x[1] <= R)ans += a[i].z;
		return ans + cal(rt,l,r,L,R);
	}
}t;


int main(){
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout); 
	int op = read();n = read();
	B = 15000;
	while(1){
		int op = read();
		if(op == 3)break;
		if(op == 1){
			int x = read()^las,y = read()^las,z = read()^las;
			a[++cnt].x[0] = x,a[cnt].x[1] = y;
			a[cnt].z = z;
			if(cnt - la >= B)t.build(rt,1,cnt),la = cnt;
		}
		else{
			int l1 = read()^las,r1 = read()^las,l2 = read()^las,r2 = read()^las;
			printf("%d\n",t.ask(l1,l2,r1,r2));
		}
	}

	return 0;

}