记录编号	227352	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	葳棠殇	是否通过	通过
代码语言	C++	运行时间	13.195 s
提交时间	2016-02-18 16:25:28	内存使用	12.44 MiB

#include<stdio.h>
#include<ctype.h>
#include<algorithm>
using namespace std;
template<class T>inline void Read(T &x){
	x=0;bool flag=false;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-'){flag=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	if(flag){x=-x;}
}
bool D;
struct point{
	int d[2],mx[2],mn[2],v,l,r,sum;
	int& operator[](int x){
		return d[x];
	}
	friend bool operator == (point a,point b){
		return a[0]==b[0]&&a[1]==b[1];
	}
	friend bool operator < (point a,point b){
		return a[D]<b[D];
	}
}p[200005];
inline bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
	return x1<=X1&&X2<=x2&&y1<=Y1&&Y2<=y2;
}
inline bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
	return x1>X2||X1>x2||y1>Y2||Y1>y2;
}
struct data{
	point t[200005],now;
	int rt,cnt;
	void update(int k){
		//printf("update k=%d\n",k);
		int l=t[k].l,r=t[k].r;
		for(int i=0;i<2;i++){
			t[k].mn[i]=t[k].mx[i]=t[k][i];
			if(l){
				t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);
				t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);
			}
			if(r){
				t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);
				t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);
			}
		}
		t[k].sum=t[k].v+t[l].sum+t[r].sum;
	}
	void insert(int &k,bool D){
		//printf("insert k=%d\n",k);
		if(!k){
			k=++cnt;
			t[k][0]=t[k].mn[0]=t[k].mx[0]=now[0];
			t[k][1]=t[k].mn[1]=t[k].mx[1]=now[1];
		}
		if(now==t[k]){
			t[k].v+=now.v;
			t[k].sum+=now.v;
			return ;
		}
		if(now[D]<t[k][D]){
			//printf("left ");
			insert(t[k].l,D^1);
		}else{
			//printf("right ");
			insert(t[k].r,D^1);
		}
		update(k);
	}
	int rebuild(int l,int r,bool d){
		if(l>r){
			return 0;
		}
		int mid=(l+r)>>1;
		D=d;
		nth_element(p+l,p+mid,p+r+1);
		t[mid]=p[mid];
		t[mid].l=rebuild(l,mid-1,d^1);
		t[mid].r=rebuild(mid+1,r,d^1);
		update(mid);
		return mid;
	}
	int Query(int k,int x1,int y1,int x2,int y2){
		//printf("Query k=%d\n",k);
		if(!k){
			return 0;
		}
		int tmp=0;
		if(in(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))return t[k].sum;
		if(out(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))return 0;
		if(in(x1,y1,x2,y2,t[k][0],t[k][1],t[k][0],t[k][1]))tmp+=t[k].v;
		tmp+=Query(t[k].l,x1,y1,x2,y2)+Query(t[k].r,x1,y1,x2,y2);
		return tmp;
	}
}T;
int n,ans;
int main(){
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	int opt,x,y,x2,y2,a,m=10000;
	while(19990828){
		Read(opt);
		if(opt==0){
			Read(n);
			continue;
		}
		if(opt==3){
			break;
		}
		Read(x);Read(y);
		//x^=ans;y^=ans;
		if(opt==1){
			Read(a);
			//a^=ans;
			T.now[0]=x;
			T.now[1]=y;
			T.now.v=T.now.sum=a;
			T.insert(T.rt,0);
			if(T.cnt==m){
				for(int i=1;i<=m;i++){
					p[i]=T.t[i];
				}
				T.rt=T.rebuild(1,m,0);
				m+=10000;
			}
			//printf("^^^^^^^\n\n\n");
		}else{
			Read(x2),Read(y2);
			//x2^=ans;y2^=ans;
			ans=T.Query(T.rt,x,y,x2,y2);
			printf("%d\n",ans);
			//printf("________________\n\n\n");
		}
	}
	return 0;
}