HDU 5480 Conturbatio（二维树状数组维护区间和）

布满荆棘的人生 2022-08-08 20:28 156阅读 0赞

问题描述  
在一个n \\times mn×m的国际象棋棋盘上有很多车(Rook)，其中车可以攻击他所属的一行或一列，包括它自己所在的位置。  
现在还有很多询问，每次询问给定一个棋盘内部的矩形，问矩形内部的所有格子是否都被车攻击到？  
输入描述  
输入文件包含多组数据，第一行为数据组数TT。  
每组数据有4个正整数n , m , K , Qn,m,K,Q。  
KK为车的数量，QQ为询问的个数。  
接下来有KK行，每行两个整数x , yx,y ， 表示车所在的坐标。  
再接下来有QQ行，每行4个整数x1 , y1 , x2 , y2x1,y1,x2,y2，表示询问的矩形的左下角与右上角的坐标。

1\\leq n , m , K , Q \\leq 100,0001≤n,m,K,Q≤100,000.  
1\\leq x \\leq n , 1 \\leq y \\leq m1≤x≤n,1≤y≤m.  
1\\leq x1 \\leq x2 \\leq n , 1 \\leq y1 \\leq y2 \\leq m1≤x1≤x2≤n,1≤y1≤y2≤m.  
输出描述  
对于每组询问，输出Yes或No。  
输入样例  
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  
输出样例  
Yes  
No  
Yes  
Hint  
输入数据过大，建议使用scanf

解题思路：开两个数组，保存行和列，判断一个子矩阵能否吃到时就判断是否子矩阵的行中的某一段或者列中的某一段都是1（1代表能被车吃）即可

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<cstring>
    #include<vector>
    #include<list>
    #include<set>
    #include<string>
    #include<map>
    using namespace std;
    int heng[100005];
    int shu[100005];
    int inx[100005];
    int iny[100005];
    int sum(int end,int *p)
    {
        int sum = 0;
        while(end > 0)
        {
            sum += p[end];
            end -= end&-end;
        }
        return sum;
    }
    void pluss(int pos,int num,int n,int *p)
    {
        while(pos <= n)
        {
            p[pos] += num;
            pos += pos&-pos;
        }
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n,m,k,q;
            scanf("%d%d%d%d",&n,&m,&k,&q);
            memset(heng,0,sizeof(heng));
            memset(shu,0,sizeof(shu));
            memset(inx,0,sizeof(inx));
            memset(iny,0,sizeof(iny));
            for(int i=1; i<=k; i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                if(!heng[x])
                {
                    heng[x]=1;
                    pluss(x,1,m,inx);
                }
                if(!shu[y])
                {
                    shu[y]=1;
                    pluss(y,1,n,iny);
                }
            }
            for(int i=1;i<=q;i++)
            {
                bool mark=false;
                int x1,y1,x2,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                if(sum(x2,inx)-sum(x1-1,inx)==x2-x1+1||sum(y2,iny)-sum(y1-1,iny)==y2-y1+1) mark=true;
                if(mark) printf("Yes\n");
                else printf("No\n");
            }
        }
        return  0;
    }