本文共 2000 字，大约阅读时间需要 6 分钟。

传送门 ：

InputThe first line of the input is a integer  TT, meaning that there are  TT test cases.  Every test cases begin with four integers  n,m,K,Qn,m,K,Q.  KK is the number of Rook,  QQ is the number of queries.  Then  KK lines follow, each contain two integers  x,yx,y describing the coordinate of Rook.  Then  QQ lines follow, each contain four integers  x1,y1,x2,y2x1,y1,x2,y2 describing the left-down and right-up coordinates of query.  1≤n,m,K,Q≤100,0001≤n,m,K,Q≤100,000.  1≤x≤n,1≤y≤m1≤x≤n,1≤y≤m.  1≤x1≤x2≤n,1≤y1≤y2≤m1≤x1≤x2≤n,1≤y1≤y2≤m.  OutputFor every query output "Yes" or "No" as mentioned above.

Sample Input

22 2 1 21 11 1 1 22 1 2 22 2 2 11 11 22 1 2 2

Sample Output

YesNoYes

        题目大意：棋盘上的一个车可以吃掉同一行同一列的棋子，告诉你 车 的坐标和 一块区域，看看在这块区域中的棋子是不是都会被吃掉

        前缀和 ？ 

        树状数组？？

        代码如下    

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=100000+10;int row[maxn],col[maxn];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n,m,k,q;        memset(row,0,sizeof(row));        memset(col,0,sizeof(col));        scanf("%d%d%d%d",&n,&m,&k,&q);        while(k--)        {            int a,b;            scanf("%d%d",&a,&b);            row[a]=1,col[b]=1;  //赋值为1  有可能出现相同的不能累加        }        for(int i=1;i<=n;i++)        {            row[i]+=row[i-1];        }        for(int i=1;i<=m;i++)        {            col[i]+=col[i-1];        }        while(q--)        {            int x1,y1,x2,y2,res1,res2;            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);            res1=row[x2]-row[x1-1];            res2=col[y2]-col[y1-1];            if(res1==(x2-x1+1)||res2==(y2-y1+1))                printf("Yes\n");            else                printf("No\n");        }    }    return 0;}
       
      
     
    
   

转载地址：http://xiib.baihongyu.com/