cdq分治。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 2000500
#define maxq 400050
using namespace std;
int s,w,type,a,b,c,d,cnt=,m=,ans[maxq];
struct ques
{
int val,opt,x,y,pos,id;
}q[maxq],tmp[maxq];
int t[maxn];
bool cmp(ques a,ques b)
{
if ((a.x==b.x) && (a.y==b.y)) return a.opt<b.opt;
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int lowbit(int x)
{
return (x&(-x));
}
void add1(int x)
{
scanf("%d%d%d",&a,&b,&c);
q[++m].id=m;q[m].pos=;q[m].val=c;q[m].opt=;
q[m].x=a;q[m].y=b;
}
void add2(int x)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
cnt++;
q[++m].val=;q[m].opt=;q[m].x=c;q[m].y=d;q[m].pos=cnt;q[m].id=m;
q[++m].val=;q[m].opt=;q[m].x=a-;q[m].y=b-;q[m].pos=cnt;q[m].id=m;
q[++m].val=-;q[m].opt=;q[m].x=a-;q[m].y=d;q[m].pos=cnt;q[m].id=m;
q[++m].val=-;q[m].opt=;q[m].x=c;q[m].y=b-;q[m].pos=cnt;q[m].id=m;
}
void add(int x,int val)
{
for (int i=x;i<=w;i+=lowbit(i))
t[i]+=val;
}
int query(int x)
{
int ret=;
for (int i=x;i>=;i-=lowbit(i))
ret+=t[i];
return ret;
}
void cdq(int left,int right)
{
if (left==right) return;
int mid=left+right>>;
int l1=left,l2=mid+;
for (int i=left;i<=right;i++)
{
if ((q[i].id<=mid) && (!q[i].opt)) add(q[i].y,q[i].val);
else if ((q[i].id>mid) && (q[i].opt)) ans[q[i].pos]+=q[i].val*query(q[i].y);
}
for (int i=left;i<=right;i++)
if ((q[i].id<=mid) && (!q[i].opt)) add(q[i].y,-q[i].val);
for (int i=left;i<=right;i++)
{
if (q[i].id<=mid) tmp[l1++]=q[i];
else tmp[l2++]=q[i];
}
for (int i=left;i<=right;i++)
q[i]=tmp[i];
cdq(left,mid);cdq(mid+,right);
}
int main()
{
scanf("%d%d",&s,&w);
while (scanf("%d",&type)!=EOF)
{
if (type==) break;
if (type==) add1(cnt);
else add2(cnt);
}
sort(q+,q+m+,cmp);
cdq(,m);
for (int i=;i<=cnt;i++)
printf("%d\n",ans[i]);
return ;
}