hdu 5480|| bestcoder 　　＃５７　div 2　Conturbatio（前缀和｜｜树状数组）

Conturbatio

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

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

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

BestCoder Round #57 (div.2)

比较水．

唯一一点需要注意的是...

可能有重复元素...

因为我的思路是用两棵一维树状数组搞..

每个点标记为1

然后看矩形的两个方向中是否至少有一个方向上和等于长度...

所以这样如果有重复元素的话，不处理会出错..　

但实际上又没修改..直接前缀和就好了．．．

树状数组个毛线．．．

不过看到还有人线段树搞得233333

  1 /*************************************************************************
  2     > File Name: code/bc/#57/1002.cpp
  3     > Author: 111qqz
  4     > Email: rkz2013@126.com 
  5     > Created Time: 2015年09月26日 星期六 19时31分10秒
  6  ************************************************************************/
  7 
  8 #include<iostream>
  9 #include<iomanip>
 10 #include<cstdio>
 11 #include<algorithm>
 12 #include<cmath>
 13 #include<cstring>
 14 #include<string>
 15 #include<map>
 16 #include<set>
 17 #include<queue>
 18 #include<vector>
 19 #include<stack>
 20 #include<cctype>
 21 #define y1 hust111qqz
 22 #define yn hez111qqz
 23 #define j1 cute111qqz
 24 #define ms(a,x) memset(a,x,sizeof(a))
 25 #define lr dying111qqz
 26 using namespace std;
 27 #define For(i, n) for (int i=0;i<int(n);++i)  
 28 typedef long long LL;
 29 typedef double DB;
 30 const int inf = 0x3f3f3f3f;
 31 const int N=1E5+7;
 32 int c[N],d[N];
 33 int n,m,K,Q;
 34 bool vx[N],vy[N];
 35 
 36 int lowbit(int x)
 37 {
 38     return x&(-x);
 39 }
 40 
 41 void update ( int x,int delta)
 42 {
 43     for ( int i = x ; i  <= n ; i = i + lowbit(i))
 44     {
 45     c[i] = c[i] + delta;
 46     }
 47 }
 48 
 49 LL sum ( int x)
 50 {
 51     LL res = 0 ;
 52     for ( int i = x ; i >= 1 ; i = i - lowbit(i))
 53     {
 54      res  = res  + c[i];
 55     }
 56     return res;
 57 }
 58 
 59 void update2( int y,int delta)
 60 {
 61     for ( int i = y ; i <= m ; i = i + lowbit(i))
 62     {
 63     d[i] = d[i] + delta;
 64     }
 65 }
 66 
 67 LL sum2( int y)
 68 {
 69     LL res = 0 ;
 70     for ( int i = y  ;  i >= 1 ; i = i - lowbit(i))
 71     {
 72     res = res + d[i];
 73     }
 74     return res;
 75 
 76 }
 77 int main()
 78 {
 79   #ifndef  ONLINE_JUDGE 
 80    freopen("in.txt","r",stdin);
 81   #endif
 82    int T;
 83        scanf("%d",&T);
 84    while (T--)
 85     {
 86     ms(c,0);
 87     ms(d,0);
 88     memset(vx,false,sizeof(vx));
 89     memset(vy,false,sizeof(vy));
 90     scanf("%d %d %d %d",&n,&m,&K,&Q);
 91     for ( int i  = 0 ; i <K ; i++)
 92     {
 93         int x,y;
 94         scanf("%d %d",&x,&y);
 95         if (!vx[x])
 96         {
 97              update (x,1);
 98         vx [x] = true;
 99         }
100         if (!vy[y])
101         {
102         update2 (y,1);
103         vy[y] = true;
104         }
105         
106     }
107     for ( int i = 0 ; i < Q ; i++)
108     {
109         int x1,y1,x2,y2;
110         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
111         int xx = sum(x2)-sum(x1-1);
112         int yy = sum2(y2)-sum2(y1-1);
113       //  cout<<"sum(x2):"<<sum(x2)<<endl;
114       //  cout<<"sum(x1-1):"<<sum(x1-1)<<endl;
115       //  cout<<"sum(y2):"<<sum(y2)<<endl;
116       //  cout<<"sum(y1-1)"<<sum(y1-1)<<endl;
117       //  cout<<"xx:"<<xx<<endl;
118       //  cout<<"yy:"<<yy<<endl;
119         if (xx>=x2-x1+1||yy>=y2-y1+1)
120         {
121         puts("Yes");
122         }
123         else
124         {
125         puts("No");
126         }
127          
128     }
129     }
130   
131    
132  #ifndef ONLINE_JUDGE  
133   fclose(stdin);
134   #endif
135     return 0;
136 }

View Code

hdu 5480|| bestcoder ＃５７ div 2 Conturbatio（前缀和｜｜树状数组）

Conturbatio

hdu 5480|| bestcoder 　　＃５７　div 2　Conturbatio（前缀和｜｜树状数组）