hdu 5480|| bestcoder ＃５７ div 2 Conturbatio（前缀和｜｜树状数组）
比较水．
唯一一点需要注意的是...
可能有重复元素...
因为我的思路是用两棵一维树状数组搞..
每个点标记为1
然后看矩形的两个方向中是否至少有一个方向上和等于长度...
所以这样如果有重复元素的话，不处理会出错..
但实际上又没修改..直接前缀和就好了．．．
树状数组个毛线．．．
不过看到还有人线段树搞得233333
/*************************************************************************
> File Name: code/bc/#57/1002.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年09月26日 星期六 19时31分10秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#include<cctype>
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define ms(a,x) memset(a,x,sizeof(a))
18#define lr dying111qqz
19using namespace std;
20#define For(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef double DB;
23const int inf = 0x3f3f3f3f;
24const int N=1E5+7;
25int c[N],d[N];
26int n,m,K,Q;
27bool vx[N],vy[N];
1int lowbit(int x)
2{
3 return x&(-x);
4}
1void update ( int x,int delta)
2{
3 for ( int i = x ; i <= n ; i = i + lowbit(i))
4 {
5 c[i] = c[i] + delta;
6 }
7}
1LL sum ( int x)
2{
3 LL res = 0 ;
4 for ( int i = x ; i >= 1 ; i = i - lowbit(i))
5 {
6 res = res + c[i];
7 }
8 return res;
9}
1void update2( int y,int delta)
2{
3 for ( int i = y ; i <= m ; i = i + lowbit(i))
4 {
5 d[i] = d[i] + delta;
6 }
7}
1LL sum2( int y)
2{
3 LL res = 0 ;
4 for ( int i = y ; i >= 1 ; i = i - lowbit(i))
5 {
6 res = res + d[i];
7 }
8 return res;
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("in.txt","r",stdin);
6 #endif
7 int T;
8 scanf("%d",&T);
9 while (T--)
10 {
11 ms(c,0);
12 ms(d,0);
13 memset(vx,false,sizeof(vx));
14 memset(vy,false,sizeof(vy));
15 scanf("%d %d %d %d",&n,&m,&K,&Q);
16 for ( int i = 0 ; i <K ; i++)
17 {
18 int x,y;
19 scanf("%d %d",&x,&y);
20 if (!vx[x])
21 {
22 update (x,1);
23 vx [x] = true;
24 }
25 if (!vy[y])
26 {
27 update2 (y,1);
28 vy[y] = true;
29 }
1 }
2 for ( int i = 0 ; i < Q ; i++)
3 {
4 int x1,y1,x2,y2;
5 scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
6 int xx = sum(x2)-sum(x1-1);
7 int yy = sum2(y2)-sum2(y1-1);
8 // cout<<"sum(x2):"<<sum(x2)<<endl;
9 // cout<<"sum(x1-1):"<<sum(x1-1)<<endl;
10 // cout<<"sum(y2):"<<sum(y2)<<endl;
11 // cout<<"sum(y1-1)"<<sum(y1-1)<<endl;
12 // cout<<"xx:"<<xx<<endl;
13 // cout<<"yy:"<<yy<<endl;
14 if (xx>=x2-x1+1||yy>=y2-y1+1)
15 {
16 puts("Yes");
17 }
18 else
19 {
20 puts("No");
21 }
}
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}