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