记录编号	364977	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	13.754 s
提交时间	2017-01-18 21:31:17	内存使用	7.94 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010,B=1500;
int d;
struct node{
	int x[2],l[2],r[2],w,sum;
	node *ch[2];
	bool operator<(const node &a)const{return x[d]<a.x[d];}
}a[maxn],*null=a,*root=null;
void build(int,int,int,node*&);
void query(node*);
int n=0,tmp,l[2],r[2],x[B+10][2],w[B+10],cnt=0,ans=0;
int main(){
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	null->l[0]=null->l[1]=10000000;
	null->r[0]=null->r[1]=-10000000;
	scanf("%*d%*d");
	while(scanf("%d",&tmp)==1&&tmp!=3){
		if(tmp==1){
			cnt++;
			scanf("%d%d%d",&x[cnt][0],&x[cnt][1],&w[cnt]);
			if(cnt==B){
				for(int i=1;i<=cnt;i++){
					a[i+n].x[0]=x[i][0];
					a[i+n].x[1]=x[i][1];
					a[i+n].w=w[i];
				}
				build(1,n+=B,0,root);
				cnt=0;
			}
		}
		else{
			scanf("%d%d%d%d",&l[0],&l[1],&r[0],&r[1]);
			ans=0;
			query(root);
			for(int i=1;i<=cnt;i++)if(l[0]<=x[i][0]&&l[1]<=x[i][1]&&x[i][0]<=r[0]&&x[i][1]<=r[1])ans+=w[i];
			printf("%d\n",ans);
		}
	}
	return 0;
}
void build(int l,int r,int k,node *&rt){
	if(l>r){
		rt=null;
		return;
	}
	int mid=(l+r)>>1;
	d=k;
	nth_element(a+l,a+mid,a+r+1);
	rt=a+mid;
	build(l,mid-1,k^1,rt->ch[0]);
	build(mid+1,r,k^1,rt->ch[1]);
	rt->l[0]=min(rt->x[0],min(rt->ch[0]->l[0],rt->ch[1]->l[0]));
	rt->l[1]=min(rt->x[1],min(rt->ch[0]->l[1],rt->ch[1]->l[1]));
	rt->r[0]=max(rt->x[0],max(rt->ch[0]->r[0],rt->ch[1]->r[0]));
	rt->r[1]=max(rt->x[1],max(rt->ch[0]->r[1],rt->ch[1]->r[1]));
	rt->sum=rt->w+rt->ch[0]->sum+rt->ch[1]->sum;
}
void query(node *rt){
	if(l[0]<=rt->l[0]&&l[1]<=rt->l[1]&&rt->r[0]<=r[0]&&rt->r[1]<=r[1]){
		ans+=rt->sum;
		return;
	}
	if(r[0]<rt->l[0]||r[1]<rt->l[1]||l[0]>rt->r[0]||l[1]>rt->r[1])return;
	if(l[0]<=rt->x[0]&&l[1]<=rt->x[1]&&rt->x[0]<=r[0]&&rt->x[1]<=r[1])ans+=rt->w;
	query(rt->ch[0]);
	query(rt->ch[1]);
}