http://codeforces.com/problemset/problem/552/A
题意:一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。
思路:树状数组搞得…然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
/* *********************************************** Author :111qqz Created Time :2015年12月14日 星期一 14时01分14秒 File Name :code/cf/problem/552A.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E2+7; int n; int c[N][N]; struct Point { int x1,y1,x2,y2; void input() { scanf("%d %d",&x1,&y1); scanf("%d %d",&x2,&y2); } }p[N]; int lowbit( int x) { return x&(-x); } void update( int x,int y,int delta) { for ( int i = x ; i <= 105 ; i += lowbit(i)) { for ( int j = y ; j <= 105 ; j +=lowbit(j)) { c[i][j] +=delta; } } } int sum ( int x,int y) { int res = 0 ; for ( int i = x; i>= 1 ; i-=lowbit(i)) { for ( int j = y ; j >= 1 ; j-=lowbit(j)) { res += c[i][j]; // cout<<"res:"<<res<<endl; } } return res; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif ms(c,0); cin>>n; for ( int i = 0 ; i < n; i++) p[i].input(); // puts("aahhhhhh"); for ( int i = 0 ; i <n ; i++) { update(p[i].x2+1,p[i].y2+1,1); // cout<<"www?"<<endl; update(p[i].x2+1,p[i].y1,-1); update(p[i].x1,p[i].y2+1,-1); update(p[i].x1,p[i].y1,1); // puts("yyyyepppppp"); } int ans = 0; for ( int i = 1 ; i <= 101 ; i ++) for ( int j = 1 ; j <= 101; j++) ans += sum(i,j); cout<<ans<<endl; #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!