hdu 5480(维护前缀和+思路题)

时间：2023-03-10 00:16:03
hdu 5480(维护前缀和+思路题)

Conturbatio

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 786    Accepted Submission(s): 358

Problem Description
There are many rook on a chessboard, a rook can attack the row and column it belongs, including its own place.

There
are also many queries, each query gives a rectangle on the chess board,
and asks whether every grid in the rectangle will be attacked by any
rook?

Input
The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with four integers n,m,K,Q.
K is the number of Rook, Q is the number of queries.

Then K lines follow, each contain two integers x,y describing the coordinate of Rook.

Then Q lines follow, each contain four integers x1,y1,x2,y2 describing the left-down and right-up coordinates of query.

1≤n,m,K,Q≤100,000.

1≤x≤n,1≤y≤m.

1≤x1≤x2≤n,1≤y1≤y2≤m.

Output
For every query output "Yes" or "No" as mentioned above.
Sample Input
2
2 2 1 2
1 1
1 1 1 2
2 1 2 2
2 2 2 1
1 1
1 2
2 1 2 2
Sample Output
Yes
No
Yes
Hint

Huge input, scanf recommended.

Source
题意:在一个棋盘上有一些"车"，他能够攻击到与它同一行或者同一列的棋盘上的所有的格子，现在给出K个棋子的坐标，然后有Q组询问，每一次询问(x1,y1,x2,y2)这个方格内的所有棋子是否能够全部被攻击到。
题解:维护前缀和,统计 (x1-x2) 这一段区间里面的被攻击到的行的数量，统计(y1-y2)这一段区间里面的被攻击到的列的数量,如果sum(x1~x2) == x2-x1+1 ，那么这段区间全部能够被攻击到,列也就不用考虑了，对列的考虑亦如此。
#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

const int N = ;

int flag_x[N],flag_y[N];

int main()

{

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        int n,m,k,q;

        scanf("%d%d%d%d",&n,&m,&k,&q);

        memset(flag_x,,sizeof(flag_x));

        memset(flag_y,,sizeof(flag_y));

        int x,y;

        for(int i=;i<=k;i++){

            scanf("%d%d",&x,&y);

            flag_x[x] = ;

            flag_y[y] = ;

        }

        for(int i=;i<=n;i++){

            flag_x[i]+= flag_x[i-];

        }

        for(int i=;i<=m;i++){

            flag_y[i] += flag_y[i-];

        }

        while(q--){

            int x1,y1,x2,y2;

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            if(flag_x[x2]-flag_x[x1-]==x2-x1+||flag_y[y2]-flag_y[y1-]==y2-y1+) printf("Yes\n");

            else printf("No\n");

        }

    }

    return ;

}

相关文章