hdu 5480 Conturbatio （前缀和）

用两个数组，分别记录车所占的行和列的前缀和，每次查询可直接计算。

多亏这道题二维数组开不下，否则还真有可能想不到这种方法。

/*
Title :Conturbatio
Status:AC

By wf,2015 09 26
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define FOR(i,s,t) for(int i = (s) ; i <= (t) ; ++i )

typedef long long ll;
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1e5+5;

//std::vector<int> a[maxn];
int h[maxn],l[maxn];
int n,m,k,q,x,y,xx,yy;
int n1,n2;

int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&m,&k,&q);
		memset(h,0,sizeof h);
		memset(l,0,sizeof l);
		
		while(k--){
			scanf("%d%d",&x,&y);
			if(h[x]==0){
			 	h[x]=1;
			}
			if(l[y]==0){
				l[y]=1;
			}
		}
		for(int i=1;i<=n;++i){
			h[i]=h[i-1]+h[i];
		}
		for(int j=1;j<=m;++j){
			l[j]=l[j-1]+l[j];
		}
		while(q--){
			scanf("%d%d%d%d",&x,&y,&xx,&yy);
			
			n1=h[xx]-h[x-1];
			n2=l[yy]-l[y-1];

			int tmp=n1*(yy-y+1)+n2*(xx-x+1)-n1*n2;
			int all=(xx-x+1)*(yy-y+1);
			
			if(tmp==all)
				printf("Yes
" );
			else
				printf("No
");
		}

	}
	return 0;
}