记录编号	161745	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	3.387 s
提交时间	2015-05-09 21:45:54	内存使用	46.74 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int cmd,maxn=2000010,n,tot=0,ans[10010]={0},Bit[2000010]={0},H[160010];
class miku
{
	public:
	int x,y,k,s;
	int q;
	miku(){}
	miku(int x1,int y1,int k1,int v1,int t)
	{
		x=x1,y=y1,k=k1,s=v1,q=t;
	}
	bool operator <(const miku a) const
	{
		return x<a.x;
	}
};
miku Q[2000010];
int lowbit(int x)
{
	return x&-x;
}
int query(int x)
{
	int re=0;
	while(x>0){re+=Bit[x];x-=lowbit(x);}
	return re;
}
void add(int x,int y)
{
	while(x<=n){Bit[x]+=y;x+=lowbit(x);}
}
void solve(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	sort(Q+l,Q+mid+1);sort(Q+mid+1,Q+r+1);
	int L=l,inq=0;
	for(int i=mid+1;i<=r;i++)
	{
		if(Q[i].k==2)
		{
		    while(L<=mid&&Q[L].x<=Q[i].x)
		    {
			    if(Q[L].k==1)
				{
				add(Q[L].y,Q[L].s);
				H[++inq]=L;
			    }
			L++;
		   }
		   ans[Q[i].q]+=Q[i].s*query(Q[i].y);
		}
		//cout<<i<<" "<<Q[i].q<<" "<<Q[i].k<<" "<<Q[i].s<<endl;
	}
	for(int i=1;i<=inq;i++)
		add(Q[H[i]].y,-Q[H[i]].s);
}
void push(int x,int y,int k,int v,int t)
{
	if(x>0&&y>0)
	Q[++tot]=miku(x,y,k,v,t);
}
int main()
{
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	int x1,y1,x2,y2,v,tail=0;
	while(scanf("%d",&cmd)&&cmd!=3)
	{
		if(cmd==0) 
		{
			scanf("%d",&n);
		}
		if(cmd==1)
		{
			scanf("%d%d%d",&x1,&x2,&v);
			push(x1,x2,1,v,0);
			//printf("1");
		}
		if(cmd==2)
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			tail++;
			push(x2,y2,2,1,tail);
			push(x1-1,y1-1,2,1,tail);
			push(x1-1,y2,2,-1,tail);
			push(x2,y1-1,2,-1,tail);
			//printf("2");
		}
	}
	solve(1,tot);
	for(int i=1;i<=tail;i++) printf("%d\n",ans[i]);
	return 0;
}