【POI2008】STR

本文主要是介绍【POI2008】STR，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意
给出一个平面内的n个点，有一系列询问形如: $x_0,y_0,x_1,y_1$ ，输出平面的点中更接近 $(x_0,y_0)$ 的个数，更接近 $(x_1,y_1)$ 的个数，与两点距离相等的点的个数。

主要思想
可以按照询问分6种情况讨论!
情况一
情况二
情况三
情况四
情况五
情况六
以上六种情况中， $p_1$ 表示第一个点， $p_2$ 表示第二个点，他们之间的关系有六种，前三种分别为，他们组成的长方形的长与纵轴平行，他们组成的长方形的长与横轴平行，他们组成了一个正方形，后三种类似。每个图被分为三个部分：
1. 实线与阴影部分
2. 实线与阴影部分外偏 $p_1$ 的部分
3. 实线与阴影部分外偏 $p_2$ 的部分
对于每一种情况，将分出的部分再分成几块来算，用某个数据结构（比如树状数组）来维护就好了。
下面附一下代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<queue>
#include<functional>
#include<set>
#include<map>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define MAXN 100010typedef double db;using namespace std;int get(){char ch;while (ch=getchar(),(ch<'0'||ch>'9')&& ch!='-');char c=ch;int s=(c!='-')*c-48;while (ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-48;return c=='-'?-s:s;
}int n,m,z,p;
struct point{int x,y;db v;
}a[MAXN],b[MAXN];
int hx[MAXN],kx,hy[MAXN],ky,tree[MAXN],c[MAXN];
struct question{db x1,x2,y1,y2;int ty,ans1,ans2,ans3;db v1,v2;bool bz;
}q[MAXN];void gettype(int x1,int y1,int x2,int y2,int i){q[i].bz=0;if(y1<y2){x1^=x2^=x1^=x2;y1^=y2^=y1^=y2;q[i].bz=1;}q[i].x1=x1;q[i].y1=y1;q[i].x2=x2;q[i].y2=y2;if (x1<x2){if (y1-y2>x2-x1)q[i].ty=1;if (y1-y2<x2-x1)q[i].ty=2;if (y1-y2==x2-x1)q[i].ty=3;}else{if (y1-y2>x1-x2)q[i].ty=4;if (y1-y2<x1-x2)q[i].ty=5;if (y1-y2==x1-x2)q[i].ty=6;}
}bool cmp1(point i,point j){if (i.y!=j.y)return i.y<j.y;return i.x<j.x;
}bool cmp2(point i,point j){if (i.x!=j.x)return i.x<j.x;return i.y<j.y;
}bool cmp3(int i,int j){if (q[i].v1!=q[j].v1)return q[i].v1<q[j].v1;return q[i].v2<q[j].v2;
}bool cmp4(point i,point j){if (i.v!=j.v)return i.v<j.v;return i.x<j.x;
}void add(int x){while (x<=z){tree[x]++;x+=x & -x;}
}int getsum(int x){int ans(0);while (x){ans+=tree[x];x=x-(x&-x);}return ans;
}int askx(db x){int l=1,r=kx,ans(0);while (l<=r){int mid=(l+r)/2;if (hx[mid]>x)r=mid-1;else{l=mid+1;ans=mid;}}return ans;
}int asky(db x){int l=1,r=ky,ans(0);while (l<=r){int mid=(l+r)/2;if (hy[mid]>x)r=mid-1;else{l=mid+1;ans=mid;}}return ans;
}void type1(){int h1=1,tot=0;fo(i,1,p)if (q[i].ty==1)c[++tot]=i;sort(a+1,a+1+z,cmp1);ky=0;fo(i,1,z)if (a[i].y>a[i-1].y)hy[++ky]=a[i].y;sort(a+1,a+1+z,cmp2);kx=0;fo(i,1,z)if (a[i].x>a[i-1].x)hx[++kx]=a[i].x;fo(i,1,tot){int x=c[i];q[x].v1=q[x].x1;q[x].v2=q[x].y1-db(q[x].x2-q[x].x1+q[x].y1-q[x].y2)/2;}sort(c+1,c+1+tot,cmp3);fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].x){int x=c[h1++];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans2+=t2;q[x].ans1+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}add(asky(a[i].y));}while(h1<=tot){int x=c[h1++];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans2+=t2;q[x].ans1+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}fo(i,1,tot){int x=c[i];q[x].v1=q[x].x2;q[x].v2=q[x].y2+db(q[x].x2-q[x].x1+q[x].y1-q[x].y2)/2;}sort(c+1,c+1+tot,cmp3);fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].x){int x=c[h1--];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans2+=t2;q[x].ans1+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}add(asky(a[i].y));}while(h1){int x=c[h1--];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans2+=t2;q[x].ans1+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}fo(i,1,z)a[i].v=a[i].y-a[i].x;sort(a+1,a+1+z,cmp4);fo(i,1,tot){int x=c[i];q[x].v1=q[x].v2-q[x].v1;q[x].v2=0;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z)tree[i]=0;fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].v){int x=c[h1++];if (q[x].x2!=q[x].x1)q[x].ans2+=getsum(askx(q[x].x2))-getsum(askx(q[x].x1-1));}add(askx(a[i].x));}while (h1<=tot){int x=c[h1++];if (q[x].x2!=q[x].x1)q[x].ans2+=getsum(askx(q[x].x2))-getsum(askx(q[x].x1-1));}fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].v){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x2))-getsum(askx(q[x].x1-1));}add(askx(a[i].x));}while (h1){int x=c[h1--];if (q[x].x2!=q[x].x1)q[x].ans1+=getsum(askx(q[x].x2))-getsum(askx(q[x].x1-1));}h1=1;int l;a[0].v=a[1].v-1;a[z+1].v=a[z].v+1;fo(i,1,z+1){if (a[i].v>a[i-1].v){while(h1<=tot&&q[c[h1]].v1<a[i-1].v)h1++;while(h1<=tot&&q[c[h1]].v1==a[i-1].v){int ll=l,rr=i-1,a1(-1),a2(-1),x=c[h1++];while (ll<=rr){int mid=(ll+rr)/2;if (a[mid].x<q[x].x1)ll=mid+1;else{rr=mid-1;a1=mid;}}ll=l;rr=i-1;while(ll<=rr){int mid=(ll+rr)/2;if (a[mid].x>q[x].x2)rr=mid-1;else{ll=mid+1;a2=mid;}}if (a1==-1||a2==-1)continue;q[x].ans3+=a2-a1+1;}l=i;}}
}void type2(){int h1,tot(0);fo(i,1,p)if (q[i].ty==2)c[++tot]=i;sort(a+1,a+1+z,cmp1);fo(i,1,tot){int x=c[i];q[x].v2=q[x].x2-db(q[x].x2-q[x].x1+q[x].y1-q[x].y2)/2;q[x].v1=q[x].y2;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z)tree[i]=0;fo(i,1,z){while(h1<=tot&&q[c[h1]].v1<=a[i].y){int x=c[h1++];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=i-1;int l1=q[x].ans1,l2=q[x].ans2,l3=q[x].ans3;q[x].ans1+=t2;q[x].ans2+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans1+=t1-t2;}add(askx(a[i].x));}while(h1<=tot){int x=c[h1++];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=z;int l1=q[x].ans1,l2=q[x].ans2,l3=q[x].ans3;q[x].ans1+=t2;q[x].ans2+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans1+=t1-t2;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v2=q[x].x1+db(q[x].x2-q[x].x1+q[x].y1-q[x].y2)/2;q[x].v1=q[x].y1;}sort(c+1,c+1+tot,cmp3);h1=tot;fd(i,z,1){while(h1&&q[c[h1]].v1>=a[i].y){int x=c[h1--];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=z-i;int l1=q[x].ans1,l2=q[x].ans2,l3=q[x].ans3;q[x].ans2+=t3-t1;q[x].ans1+=t2;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans1+=t1-t2;}add(askx(a[i].x));} while(h1){int x=c[h1--];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=z;int l1=q[x].ans1,l2=q[x].ans2,l3=q[x].ans3;q[x].ans2+=t3-t1;q[x].ans1+=t2;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans1+=t1-t2;}fo(i,1,z)a[i].v=a[i].y-a[i].x;sort(a+1,a+1+z,cmp4);fo(i,1,tot){int x=c[i];q[x].v1=q[x].v1-q[x].v2;q[x].v2=0;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z)tree[i]=0;fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].v){int x=c[h1++];q[x].ans2+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}add(asky(a[i].y));}while (h1<=tot){int x=c[h1++];q[x].ans2+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].v){int x=c[h1--];q[x].ans1+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}add(asky(a[i].y));}while (h1){int x=c[h1--];q[x].ans1+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}h1=1;int l=1;a[0].v=a[1].v-1;a[z+1].v=a[z].v+1;fo(i,1,z+1){if (a[i].v>a[i-1].v){while(h1<=tot&&q[c[h1]].v1<a[i-1].v)h1++;while(h1<=tot&&q[c[h1]].v1==a[i-1].v){int ll=l,rr=i-1,a1(-1),a2(-1),x=c[h1++];db len=(q[x].x2-q[x].x1+q[x].y1-q[x].y2)/2;while (ll<=rr){int mid=(ll+rr)/2;if (a[mid].x<q[x].x2-len)ll=mid+1;else{rr=mid-1;a1=mid;}}ll=l;rr=i-1;while(ll<=rr){int mid=(ll+rr)/2;if (a[mid].x>q[x].x1+len)rr=mid-1;else{ll=mid+1;a2=mid;}}if (a1==-1||a2==-1)continue;q[x].ans3+=a2-a1+1;}l=i;}}
}void type3(){int h1,tot(0);fo(i,1,p)if (q[i].ty==3)c[++tot]=i;fo(i,1,z)tree[i]=0;sort(a+1,a+1+z,cmp2);fo(i,1,tot){int x=c[i];q[x].v1=q[x].x1;q[x].v2=q[x].y2;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z){while(h1<=tot&&q[c[h1]].v1<=a[i].x){int x=c[h1++];int t1=getsum(asky(q[x].v2)),t2=getsum(ky);q[x].ans3+=t1;q[x].ans1+=t2-t1;}add(asky(a[i].y));}while(h1<=tot){int x=c[h1++];int t1=getsum(asky(q[x].v2)),t2=getsum(ky);q[x].ans3+=t1;q[x].ans1+=t2-t1;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v1=q[x].x2;q[x].v2=q[x].y1;}sort(c+1,c+1+tot,cmp3);h1=tot;fd(i,z,1){while(h1&&q[c[h1]].v1>=a[i].x){int x=c[h1--];int t1=getsum(ky),t2=getsum(asky(q[x].v2-1));q[x].ans2+=t2;q[x].ans3+=t1-t2;}add(asky(a[i].y));}while(h1){int x=c[h1--];int t1=getsum(ky),t2=getsum(asky(q[x].v2-1));q[x].ans2+=t2;q[x].ans3+=t1-t2;}fo(i,1,z)a[i].v=a[i].y-a[i].x;sort(a+1,a+1+z,cmp4);fo(i,1,tot){int x=c[i];q[x].v1=q[x].v2-q[x].v1;q[x].v2=0;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z)tree[i]=0;fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].v){int x=c[h1++];q[x].ans2+=getsum(askx(q[x].x2))-getsum(askx(q[x].x1));q[x].ans3+=getsum(askx(q[x].x1))-getsum(askx(q[x].x1-1));}add(askx(a[i].x));}while (h1<=tot){int x=c[h1++];q[x].ans2+=getsum(askx(q[x].x2))-getsum(askx(q[x].x1));q[x].ans3+=getsum(askx(q[x].x1))-getsum(askx(q[x].x1-1));}fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].v){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x2-1))-getsum(askx(q[x].x1-1));q[x].ans3+=getsum(askx(q[x].x2))-getsum(askx(q[x].x2-1));}add(askx(a[i].x));}while (h1){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x2-1))-getsum(askx(q[x].x1-1));q[x].ans3+=getsum(askx(q[x].x2))-getsum(askx(q[x].x2-1));}h1=1;int l;a[0].v=a[1].v-1;a[z+1].v=a[z].v+1;fo(i,1,z+1){if (a[i].v>a[i-1].v){while(h1<=tot&&q[c[h1]].v1<a[i-1].v)h1++;while(h1<=tot&&q[c[h1]].v1==a[i-1].v){int ll=l,rr=i-1,a1(-1),a2(-1),x=c[h1++];while (ll<=rr){int mid=(ll+rr)/2;if (a[mid].x<q[x].x1)ll=mid+1;else{rr=mid-1;a1=mid;}}ll=l;rr=i-1;while(ll<=rr){int mid=(ll+rr)/2;if (a[mid].x>q[x].x2)rr=mid-1;else{ll=mid+1;a2=mid;}}if (a1==-1||a2==-1)continue;q[x].ans3+=a2-a1+1;}l=i;}}
}void type4(){int h1,tot(0);fo(i,1,p)if (q[i].ty==4)c[++tot]=i;sort(a+1,a+1+z,cmp2);fo(i,1,tot){int x=c[i];q[x].v1=q[x].x2;q[x].v2=q[x].y2+db(q[x].x1-q[x].x2+q[x].y1-q[x].y2)/2;}fo(i,1,z)tree[i]=0;sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z){while(h1<=tot&&q[c[h1]].v1<=a[i].x){int x=c[h1++];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans1+=t3-t1;q[x].ans2+=t2;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}add(asky(a[i].y));}while(h1<=tot){int x=c[h1++];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans1+=t3-t1;q[x].ans2+=t2;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v1=q[x].x1;q[x].v2=q[x].y1-db(q[x].x1-q[x].x2+q[x].y1-q[x].y2)/2;}sort(c+1,c+1+tot,cmp3);h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].x){int x=c[h1--];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans1+=t3-t1;q[x].ans2+=t2;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}add(asky(a[i].y));}while (h1){int x=c[h1--];int t1=getsum(asky(q[x].v2)),t2=getsum(asky(q[x].v2-1)),t3=getsum(ky);q[x].ans1+=t3-t1;q[x].ans2+=t2;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v1=q[x].v1+q[x].v2;q[x].v2=0;}sort(c+1,c+1+tot,cmp3);fo(i,1,z)a[i].v=a[i].x+a[i].y;sort(a+1,a+1+z,cmp4);h1=1;fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].v){int x=c[h1++];q[x].ans2+=getsum(askx(q[x].x1))-getsum(askx(q[x].x2-1));}add(askx(a[i].x));}while (h1<=tot){int x=c[h1++];q[x].ans2+=getsum(askx(q[x].x1))-getsum(askx(q[x].x2-1));}fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].v){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x1))-getsum(askx(q[x].x2-1));}add(askx(a[i].x));}while (h1){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x1))-getsum(askx(q[x].x2-1));}h1=1;int l;a[0].v=a[1].v-1;a[z+1].v=a[z].v+1;fo(i,1,z+1){if (a[i].v>a[i-1].v){while(h1<=tot&&q[c[h1]].v1<a[i-1].v)h1++;while(h1<=tot&&q[c[h1]].v1==a[i-1].v){int ll=l,rr=i-1,a1(-1),a2(-1),x=c[h1++];while (ll<=rr){int mid=(ll+rr)/2;if (a[mid].x<q[x].x2)ll=mid+1;else{rr=mid-1;a1=mid;}}ll=l;rr=i-1;while(ll<=rr){int mid=(ll+rr)/2;if (a[mid].x>q[x].x1)rr=mid-1;else{ll=mid+1;a2=mid;}}if (a1==-1||a2==-1)continue;q[x].ans3+=a2-a1+1;}l=i;}}
}void type5(){int h1,tot(0);fo(i,1,p)if (q[i].ty==5)c[++tot]=i;sort(a+1,a+1+z,cmp1);fo(i,1,tot){int x=c[i];q[x].v2=q[x].x2+db(q[x].x1-q[x].x2+q[x].y1-q[x].y2)/2;q[x].v1=q[x].y2;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z)tree[i]=0;fo(i,1,z){while(h1<=tot&&q[c[h1]].v1<=a[i].y){int x=c[h1++];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=i-1;q[x].ans2+=t2;q[x].ans1+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}add(askx(a[i].x));}while(h1<=tot){int x=c[h1++];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1));q[x].ans2+=t2;q[x].ans1+=z-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v2=q[x].x1-db(q[x].x1-q[x].x2+q[x].y1-q[x].y2)/2;q[x].v1=q[x].y1;}sort(c+1,c+1+tot,cmp3);h1=tot;fd(i,z,1){while(h1&&q[c[h1]].v1>=a[i].y){int x=c[h1--];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=z-i;q[x].ans2+=t2;q[x].ans1+=t3-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}add(askx(a[i].x));} while(h1){int x=c[h1--];int t1=getsum(askx(q[x].v2)),t2=getsum(askx(q[x].v2-1)),t3=z;q[x].ans2+=t2;q[x].ans1+=z-t1;if (int(q[x].v2)==q[x].v2)q[x].ans3+=t1-t2;else q[x].ans2+=t1-t2;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v1=q[x].v1+q[x].v2;q[x].v2=0;}sort(c+1,c+1+tot,cmp3);fo(i,1,z)a[i].v=a[i].x+a[i].y;sort(a+1,a+1+z,cmp4);h1=1;fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].v){int x=c[h1++];q[x].ans2+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}add(asky(a[i].y));}while (h1<=tot){int x=c[h1++];q[x].ans2+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].v){int x=c[h1--];q[x].ans1+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}add(asky(a[i].y));}while (h1){int x=c[h1--];q[x].ans1+=getsum(asky(q[x].y1))-getsum(asky(q[x].y2-1));}h1=1;int l=1;a[0].v=a[1].v-1;a[z+1].v=a[z].v+1;fo(i,1,z+1){if (a[i].v>a[i-1].v){while(h1<=tot&&q[c[h1]].v1<a[i-1].v)h1++;while(h1<=tot&&q[c[h1]].v1==a[i-1].v){int ll=l,rr=i-1,a1(-1),a2(-1),x=c[h1++];db len=(q[x].x1-q[x].x2+q[x].y1-q[x].y2)/2;while (ll<=rr){int mid=(ll+rr)/2;if (a[mid].x<q[x].x1-len)ll=mid+1;else{rr=mid-1;a1=mid;}}ll=l;rr=i-1;while(ll<=rr){int mid=(ll+rr)/2;if (a[mid].x>q[x].x2+len)rr=mid-1;else{ll=mid+1;a2=mid;}}if (a1==-1||a2==-1)continue;q[x].ans3+=a2-a1+1;}l=i;}}
}void type6(){int h1,tot(0);fo(i,1,p)if (q[i].ty==6)c[++tot]=i;fo(i,1,z)tree[i]=0;sort(a+1,a+1+z,cmp2);fo(i,1,tot){int x=c[i];q[x].v1=q[x].x2;q[x].v2=q[x].y1;}sort(c+1,c+1+tot,cmp3);h1=1;fo(i,1,z){while(h1<=tot&&q[c[h1]].v1<=a[i].x){int x=c[h1++];int t1=getsum(asky(q[x].v2-1)),t3=i-1;q[x].ans2+=t1;q[x].ans3+=t3-t1;}add(asky(a[i].y));}while(h1<=tot){int x=c[h1++];int t1=getsum(asky(q[x].v2-1)),t3=z;q[x].ans2+=t1;q[x].ans3+=t3-t1;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v1=q[x].x1;q[x].v2=q[x].y2;}sort(c+1,c+1+tot,cmp3);h1=tot;fd(i,z,1){while(h1&&q[c[h1]].v1>=a[i].x){int x=c[h1--];int t1=getsum(ky),t2=getsum(asky(q[x].v2));q[x].ans3+=t2;q[x].ans1+=t1-t2;}add(asky(a[i].y));}while(h1){int x=c[h1--];int t1=getsum(ky),t2=getsum(asky(q[x].v2));q[x].ans3+=t2;q[x].ans1+=t1-t2;}fo(i,1,z)tree[i]=0;fo(i,1,tot){int x=c[i];q[x].v1=q[x].v1+q[x].v2;q[x].v2=0;}sort(c+1,c+1+tot,cmp3);fo(i,1,z)a[i].v=a[i].x+a[i].y;sort(a+1,a+1+z,cmp4);h1=1;fo(i,1,z){while (h1<=tot&&q[c[h1]].v1<=a[i].v){int x=c[h1++];q[x].ans2+=getsum(askx(q[x].x1-1))-getsum(askx(q[x].x2-1));q[x].ans3+=getsum(askx(q[x].x1))-getsum(askx(q[x].x1-1));}add(askx(a[i].x));}while (h1<=tot){int x=c[h1++];q[x].ans2+=getsum(askx(q[x].x1-1))-getsum(askx(q[x].x2-1));q[x].ans3+=getsum(askx(q[x].x1))-getsum(askx(q[x].x1-1));}fo(i,1,z)tree[i]=0;h1=tot;fd(i,z,1){while (h1&&q[c[h1]].v1>=a[i].v){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x1))-getsum(askx(q[x].x2));q[x].ans3+=getsum(askx(q[x].x2))-getsum(askx(q[x].x2-1));}add(askx(a[i].x));}while (h1){int x=c[h1--];q[x].ans1+=getsum(askx(q[x].x1))-getsum(askx(q[x].x2));q[x].ans3+=getsum(askx(q[x].x2))-getsum(askx(q[x].x2-1));}h1=1;int l;a[0].v=a[1].v-1;a[z+1].v=a[z].v+1;fo(i,1,z+1){if (a[i].v>a[i-1].v){while(h1<=tot&&q[c[h1]].v1<a[i-1].v)h1++;while(h1<=tot&&q[c[h1]].v1==a[i-1].v){int ll=l,rr=i-1,a1(-1),a2(-1),x=c[h1++];while (ll<=rr){int mid=(ll+rr)/2;if (a[mid].x<q[x].x2)ll=mid+1;else{rr=mid-1;a1=mid;}}ll=l;rr=i-1;while(ll<=rr){int mid=(ll+rr)/2;if (a[mid].x>q[x].x1)rr=mid-1;else{ll=mid+1;a2=mid;}}if (a1==-1||a2==-1)continue;q[x].ans3+=a2-a1+1;}l=i;}}
}void getans(){fo(i,1,p)if (q[i].bz)printf("%d %d %d\n",q[i].ans2,q[i].ans1,q[i].ans3);else printf("%d %d %d\n",q[i].ans1,q[i].ans2,q[i].ans3);
}int main(){n=get();m=get();z=get();p=get();fo(i,1,z)a[i].x=b[i].x=get(),a[i].y=b[i].y=get();fo(i,1,p){int x1=get(),y1=get(),x2=get(),y2=get();gettype(x1,y1,x2,y2,i);}type1();type2();type3();type4();type5();type6();getans();
}