题意： n * m的棋盘， k个位置有"rook"（车），q次询问，问是否询问的方块内是否每一行都有一个车或者每一列都有一个车？ 满足一个即可
先考虑第一种情况， 第二种类似，swap一下就可以了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ;
inline int GetIdx(int l, int r){
return l + r | l != r;
}
int seg[maxn << ];
void update(int l, int r, int x, int d){
if (l == r){
seg[GetIdx(l, r)] = d;
return;
}
int mid = (l + r) >> ;
if (x <= mid){
update(l, mid, x, d);
}else{
update(mid+, r, x, d);
}
seg[GetIdx(l, r)] = min(seg[GetIdx(l, mid)], seg[GetIdx(mid+, r)]);
}
int query(int l, int r, int ua, int ub){
if (ua <= l && ub >= r){
return seg[GetIdx(l, r)];
}
int mid = (l + r) >> ;
int res = << ;
if (ua <= mid){
res = min(res, query(l, mid, ua, ub));
}
if (ub > mid){
res = min(res, query(mid+, r, ua, ub));
}
return res;
}
vector <int> line[maxn];
pair <int, int> rook[maxn << ], rec1[maxn << ], rec2[maxn << ];
bool ans[maxn << ];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n, m, k, q;
while (~scanf ("%d%d%d%d", &n, &m, &k, &q)){
for (int i = ; i < k; i++){
scanf ("%d%d", &rook[i].first, &rook[i].second);
}
for (int i = ; i < q; i++){
scanf ("%d%d%d%d", &rec1[i].first, &rec1[i].second, &rec2[i].first, &rec2[i].second);
}
for (int cas = ; cas <= ; cas++){
memset(seg, , sizeof seg);
for (int i = ; i <= n; i++){
line[i].clear();
}
for (int i = ; i < k; i++){
// 所有rook[i].first上的rook放入line里
line[rook[i].first].push_back(rook[i].second);
}
for (int i = ; i < q; i++){
//所有方格右边界线为rec2[i].first的放入line里
line[rec2[i].first].push_back(~i);
}
for (int i = ; i <= n; i++){
for (int j = ; j < line[i].size(); j++){
int tmp = line[i][j];
if (tmp < ){
tmp = ~tmp;
// 查找区间最值判断是否满足
if (query(, m, rec1[tmp].second, rec2[tmp].second) >= rec1[tmp].first){
ans[tmp] = true;
}
}else{
update(, m, tmp, i);
}
}
}
swap(n, m);
for (int i = ; i <k ;i++){
swap(rook[i].first, rook[i].second);
}
for (int i = ; i < q; i++){
swap(rec1[i].first, rec1[i].second);
swap(rec2[i].first, rec2[i].second);
}
}
for (int i = ; i < q; i++){
puts(ans[i] ? "YES" : "NO");
}
}
return ;
}