显示代码纯文本
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define ro(i,a,b) for(int i=a;i>=b;i--)
#define fo(i,a,x) for(int i=a[x];i;i=e[i].next)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;const int N=2000003;
struct Q{int x,y,v,kind,ID;}q[N];
bool cmp(Q a,Q b){return a.x<b.x;}int w,c[N],ans[N/200];
void ADD(int x,int d){while(x<=w)c[x]+=d,x+=x&(-x);}
int SUM(int x){int res=0;while(x)res+=c[x],x-=x&(-x);return res;}
void CDQ_dichotomy(int l,int r)
{
if(l==r)return;int mid=l+r>>1;
CDQ_dichotomy(l,mid);CDQ_dichotomy(mid+1,r);
sort(q+l,q+mid+1,cmp);sort(q+mid+1,q+r+1,cmp);
int j=l;
go(i,mid+1,r)
{
while(j<=mid&&q[j].x<=q[i].x)
{
if(q[j].kind)ADD(q[j].y,q[j].v);j++;
}
if(!q[i].kind)ans[q[i].ID]+=q[i].v*SUM(q[i].y);
}
go(i,l,j-1)if(q[i].kind)ADD(q[i].y,-q[i].v);
}
int main()
{
freopen("mokia.in","r",stdin);
freopen("mokia.out","w",stdout);
int t,x,y,a,b,k=0,num=0;
while(scanf("%d",&t)&&t!=3)
{
if(t==0)scanf("%d",&w);
if(t==1)
{
scanf("%d%d%d",&x,&y,&a);
q[++k]=(Q){x,y,a,1,0};
}
if(t==2)
{
scanf("%d%d%d%d",&x,&y,&a,&b);
q[++k]=(Q){a,b,1,0,++num};
q[++k]=(Q){x-1,y-1,1,0,num};
q[++k]=(Q){x-1,b,-1,0,num};
q[++k]=(Q){a,y-1,-1,0,num};
}
}
CDQ_dichotomy(1,k);
go(i,1,num)printf("%d\n",ans[i]);
return 0;
}//Paul_Guderian
Paul_Guderian