记录编号	26912	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	PurpleShadow	是否通过	通过
代码语言	C++	运行时间	3.451 s
提交时间	2011-07-29 16:03:46	内存使用	27.35 MiB

#include <cstdio>
#include <cctype>
#include <cstring>
const int N=200010,W=500010;
struct node
{
	int kind,id,time,o;
	int x,y,y1,z;
	bool operator<=(const node& t)
	{return x<=t.x;}
}P[2*N],TP[2*N];
inline int getint()
{
	char ch;
	while (!isdigit(ch=getchar()));
	int ans=ch-'0';
	for (;;)
	{
		ch=getchar();
		if (!isdigit(ch)) break;
		ans=ans*10+ch-'0';
	}
	return ans;
}
int w,n,event,ask;
void init()
{
	w=getint();n=getint();
	event=0;
	ask=0;
	for (int i=1;i<=n;++i)
	{
		P[++event].kind=getint();
		if (P[event].kind==1) 
		{
			P[event].x=getint();P[event].y=getint();P[event].z=getint();
			P[event].id=event;
		}
		else
		{
			P[event].x=getint();P[event].y=getint();P[event+1].x=getint();P[event].y1=getint();
			P[event+1].y=P[event].y;P[event+1].y1=P[event].y1;
			P[event].time=P[event+1].time=++ask;
			P[event].id=event;P[event+1].id=event+1;
			--P[event].x;
			P[event].o=-1;P[event+1].o=1;
			P[++event].kind=2;
		}
	}
}
int C[W],ans[N];
void Add(int x,int z)
{
	for (;x<=w;x+=x&(-x))
		C[x]+=z;
}
int Ask(int x)
{
	int ans=0;
	for (;x;x-=x&(-x))
		ans+=C[x];
	return ans;
}
void slove(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)>>1;
	slove(l,mid);slove(mid+1,r);
	int tl=l,tr=mid+1;
	node p;
	for (int i=l;i<=r;++i)
	{
		if (tl<=mid&&(tr>r||P[tl]<=P[tr])) p=P[tl++];else p=P[tr++];
		if (p.id<=mid&&p.kind==1) Add(p.y,p.z);
		if (p.id>mid&&p.kind==2) ans[p.time]+=(Ask(p.y1)-Ask(p.y-1))*p.o;
		TP[i]=p;
	}
	for (int i=l;i<=r;++i) 
		if (P[i].kind==1&&P[i].id<=mid) Add(P[i].y,-P[i].z);
	for (int i=l;i<=r;++i) P[i]=TP[i];
}
inline void putint(int x)
{
	static int tmp[20];
	int len=0;
	while (x>0)
	{
		tmp[len++]=x%10;
		x/=10;
	}
	if (len==0) tmp[len++]=0;
	while (len--)
		putchar(tmp[len]+'0');
	putchar('\n');
}
int main()
{
freopen("locust.in","r",stdin);
freopen("locust.out","w",stdout);
	init();
	memset(C,0,sizeof(C));
	memset(ans,0,sizeof(ans));
	slove(1,event);
	for (int i=1;i<=ask;++i)
		putint(ans[i]);
	return 0;
}