1. 因为最近的精力都放在数电试验和大作业上,所以博客不常更新了 ... 就算更新也会写一些好做的模板题
2. 依旧是扫描线 ... ym傻崽大神
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cstdio>
6 using namespace std;
7 #define lson pos<<1,L,mid
8 #define rson pos<<1|1,mid+1,R
9 #define left LL
10 #define right RR
11 const int N = 22005;
12 int seg[N<<2], left[N<<2], right[N<<2], cnt[N<<2], sum[N<<2];
13 void pushup(int pos, int L,int R){
14 if(cnt[pos]) {
15 seg[pos] = 1;
16 left[pos] = right[pos] = 1;
17 sum[pos] = R-L+1;
18 }
19 else if(L==R) {
20 seg[pos] = 0;
21 sum[pos] = 0;
22 left[pos] = right[pos] = 0;
23 }
24 else {
25 seg[pos] = seg[pos<<1] + seg[pos<<1|1] - (right[pos << 1] && left[pos << 1|1]);
26 left[pos] = left[pos<<1];
27 right[pos] = right[pos<<1|1];
28 sum[pos] = sum[pos<<1] + sum[pos <<1|1];
29 }
30 }
31 void update(int l,int r,int pos, int L,int R,int c){
32 if(l <= L && R<= r){
33 cnt[pos] += c;
34 pushup(pos, L, R);
35 return ;
36 }
37 int mid = L + R >> 1;
38 if(l <= mid) update(l,r,lson,c);
39 if(r > mid) update(l,r,rson,c);
40 pushup(pos , L, R);
41 }
42 struct segment{
43 int l,r,h,p;
44 segment(){}
45 segment(int L,int R,int H,int P): l(L), r(R), h(H), p(P){}
46 bool operator < (const segment A) const {
47 if(h == A.h) return p > A.p;
48 return h < A.h;
49 }
50 }num[N];
51 int main(){
52 int n;
53 while(~scanf("%d",&n)){
54 int len = 0;
55 for(int i=0;i<n;i++){
56 int x0,y0,x1,y1;
57 scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
58 num[len++] = segment(x0,x1-1,y0,1);
59 num[len++] = segment(x0,x1-1,y1,-1);
60 }
61 sort(num,num+len);
62 int last = 0, ans = 0;
63 memset(cnt,0,sizeof(cnt));
64 memset(sum,0,sizeof(sum));
65 memset(seg,0,sizeof(seg));
66 memset(left,0,sizeof(left));
67 memset(right,0,sizeof(right));
68 for(int i=0;i<len-1; i++){
69 update(num[i].l,num[i].r,1,-10000,10000,num[i].p);
70 ans += abs(sum[1]-last) ;
71 last = sum[1];
72 ans += (num[i+1].h-num[i].h) * seg[1] * 2;
73 }
74 ans += sum[1];
75 cout<<ans<<endl;
76 }
77 }
78
posted on 2012-06-04 20:54
西月弦 阅读(447)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目