题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=5480

题目大意

在一个$n \times m$的国际象棋棋盘上有很多车(Rook),其中车可以攻击他所属的一行或一列,包括它自己所在的位置。现在还有很多询问,每次询问给定一个棋盘内部的矩形,问矩形内部的所有格子是否都被车攻击到?

思路

这题很容易想出,只要某行或者某列都有车就行了。然后自己实现却超时了。后面用前缀和解决。。

前缀和$S_n = a_1+a_2+\cdots+a_n$

求出某项$a_n = S_n - S_{n-1}$,

求出第$i$项到第$j$项所有元素和$S_j - S_{i-1} = a_{i} + a_{i+1} + \cdots + a_{j}$

AC代码

/*************************************************************************
    > File Name: 1002.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-09-26 六 19:14:13 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int T;
int n, m, K, Q;
int sumX[100005];
int sumY[100005];

int main()
{
#ifdef Oj
    freopen("1002.in", "r", stdin);
#endif
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d%d", &n, &m, &K, &Q);
        int x0, y0;
        int x1,y1,x2,y2;
        memset(sumX, 0, sizeof(sumX));
        memset(sumY, 0, sizeof(sumY));
        for(int i=0; i<K; ++i) {
            scanf("%d%d", &x0, &y0);
            sumX[x0] = 1;
            sumY[y0] = 1;
        }
        for(int i=1; i<=max(n,m); ++i) {
            sumX[i] = sumX[i] + sumX[i-1]; // 计算前缀和
            sumY[i] = sumY[i] + sumY[i-1];
        }

        for(int i=1; i<=Q; ++i) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if(sumX[x2]-sumX[x1-1] == (x2-x1+1) || sumY[y2] - sumY[y1-1] == (y2-y1+1))
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}