HDU 5480 树状数组

 1 #include<bits/stdc++.h>
 2 #define maxn 100100
 3 using namespace std;
 4 int row[maxn],col[maxn],K,n,m,Q,x1,x2,yy1,y2;
 5 bool vis[maxn][3];
 6 inline int lowbit(int x){ return (x&-x);}
 7 inline void update(int x){
 8     while(x<=n){
 9         row[x]++;
10         x+=lowbit(x);
11     }
12 }
13 inline void Update(int y){
14     while(y<=m){
15         col[y]++;
16         y+=lowbit(y);
17     }
18 }
19 inline int getsum(int x){
20     int res=0;
21     while(x>0){
22         res+=row[x];
23         x-=lowbit(x);
24     }
25     return res;
26 }
27 inline int Getsum(int y){
28     int res=0;
29     while(y>0){
30         res+=col[y];
31         y-=lowbit(y);
32     }
33     return res;
34 }
35 int main(){
36     int T;
37     cin>>T;
38     while(T--){
39         memset(row,0,sizeof(row));
40         memset(col,0,sizeof(col));
41         memset(vis,false,sizeof(vis)); 
42         cin>>n>>m>>K>>Q;
43         for(int i=1;i<=K;i++){
44             scanf("%d%d",&x1,&yy1);
45             if(!vis[x1][1]){ 
46                 update(x1);
47                 vis[x1][1]=true;
48             }
49             if(!vis[yy1][2]){
50                 vis[yy1][2]=true;
51                 Update(yy1);
52             }
53         }
54         for(int i=1;i<=Q;i++){
55             scanf("%d%d%d%d",&x1,&yy1,&x2,&y2);
56             if((getsum(x2)-getsum(x1-1)==x2-x1+1)||(Getsum(y2)-Getsum(yy1-1)==y2-yy1+1)) printf("Yes
");
57             else printf("No
");
58         }
59     }
60     return 0;
61 }