hdu 5480|| bestcoder ＃５７ div 2 Conturbatio（前缀和｜｜树状数组）
比较水．
唯一一点需要注意的是…
可能有重复元素…
因为我的思路是用两棵一维树状数组搞..
每个点标记为1
然后看矩形的两个方向中是否至少有一个方向上和等于长度…
所以这样如果有重复元素的话，不处理会出错..
但实际上又没修改..直接前缀和就好了．．．
树状数组个毛线．．．
不过看到还有人线段树搞得233333
1/*************************************************************************
2 > File Name: code/bc/#57/1002.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月26日 星期六 19时31分10秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int c[N],d[N];
33int n,m,K,Q;
34bool vx[N],vy[N];
35
36int lowbit(int x)
37{
38 return x&(-x);
39}
40
41void update ( int x,int delta)
42{
43 for ( int i = x ; i <= n ; i = i + lowbit(i))
44 {
45 c[i] = c[i] + delta;
46 }
47}
48
49LL sum ( int x)
50{
51 LL res = 0 ;
52 for ( int i = x ; i >= 1 ; i = i - lowbit(i))
53 {
54 res = res + c[i];
55 }
56 return res;
57}
58
59void update2( int y,int delta)
60{
61 for ( int i = y ; i <= m ; i = i + lowbit(i))
62 {
63 d[i] = d[i] + delta;
64 }
65}
66
67LL sum2( int y)
68{
69 LL res = 0 ;
70 for ( int i = y ; i >= 1 ; i = i - lowbit(i))
71 {
72 res = res + d[i];
73 }
74 return res;
75
76}
77int main()
78{
79 #ifndef ONLINE_JUDGE
80 freopen("in.txt","r",stdin);
81 #endif
82 int T;
83 scanf("%d",&T);
84 while (T--)
85 {
86 ms(c,0);
87 ms(d,0);
88 memset(vx,false,sizeof(vx));
89 memset(vy,false,sizeof(vy));
90 scanf("%d %d %d %d",&n,&m,&K,&Q);
91 for ( int i = 0 ; i <K ; i++)
92 {
93 int x,y;
94 scanf("%d %d",&x,&y);
95 if (!vx[x])
96 {
97 update (x,1);
98 vx [x] = true;
99 }
100 if (!vy[y])
101 {
102 update2 (y,1);
103 vy[y] = true;
104 }
105
106 }
107 for ( int i = 0 ; i < Q ; i++)
108 {
109 int x1,y1,x2,y2;
110 scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
111 int xx = sum(x2)-sum(x1-1);
112 int yy = sum2(y2)-sum2(y1-1);
113 // cout<<"sum(x2):"<<sum(x2)<<endl;
114 // cout<<"sum(x1-1):"<<sum(x1-1)<<endl;
115 // cout<<"sum(y2):"<<sum(y2)<<endl;
116 // cout<<"sum(y1-1)"<<sum(y1-1)<<endl;
117 // cout<<"xx:"<<xx<<endl;
118 // cout<<"yy:"<<yy<<endl;
119 if (xx>=x2-x1+1||yy>=y2-y1+1)
120 {
121 puts("Yes");
122 }
123 else
124 {
125 puts("No");
126 }
127
128 }
129 }
130
131
132 #ifndef ONLINE_JUDGE
133 fclose(stdin);
134 #endif
135 return 0;
136}