算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题意描述:

    10^7 * 10^7 的平面上有N(N<50,000)个不相交的矩形。要在这个平面上放置一个长度为M(M<1,000)的线段,有多少种方法。

吐槽:

    1. 今天杭电被黑了.... 导致题解现在才出来....
    2. 果然还是自己写对拍好,想要AC总是要付出代价的么.....

算法分析:

    扫描线竖直的扫一遍,维护扫过的横向区间集合... 每个空白的一段是我们想要的可以放线段的地方...
    
    由于插入一个线段只会删除一个空白区间,增加两个空白区间。这样的话我们可以根据上一个事件点的情况,推出这个事件点的情况。
    删除一个区间同理。
    那么如何知道增加和删除的空白区间的长度呢?
    线段树维护的是实际区间的最左点和最右点。
    插入一个区间[l,r]的时候,我们同时计算出[0,l)的最右点R和(r,inf)的最左点L。
    那么新的情况就是 new = last - f(R,L) + f(R,l) + f(r,L)
    删除同理, 和求矩形周长并很像....
    
    我们加入两个左右哨兵以防止空集的情况...
    trick:
        1. n=0;
        2. m=1;
    这两个要额外讨论一下,另外离散化的时候注意一下上边和下边。
    最后还要吐槽一句: 对拍是debug最有效的手段
  
  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<cassert>
  6 using namespace std;
  7 typedef long long ll;
  8 template <typename T> inline void chkmax(T &a,const T b){ if(a < b) a=b;}
  9 template <typename T> inline void chkmin(T &a,const T b){ if(a > b) a=b;}
 10 const int N = 100005;
 11 int lt[N<<2],rt[N<<2],cnt[N<<2];
 12 int w,h,n,m,L,R;
 13 int X[N],num[N][4];
 14 struct node{
 15     int l,r,h,p;
 16     node(){}
 17     node(int L,int R,int H,int P):l(L),r(R),h(H),p(P){}
 18     bool operator < (const node &A) const {
 19         return h == A.h? p < A.p: h < A.h;
 20     }
 21 } seg[N];
 22 // segment_tree
 23 inline void upt(int pos,int l,int r){
 24     assert(!cnt[pos] && l<r);
 25     lt[pos] = lt[pos<<1] == -1 ? lt[pos<<1|1] : lt[pos<<1];
 26     rt[pos] = rt[pos<<1|1] == -1 ? rt[pos<<1] : rt[pos<<1|1];
 27 }
 28 void update(int l,int r,int pos,int ML,int MR,int ct){
 29     if(r >= MR && l <= ML){
 30         cnt[pos] += ct;
 31         if(cnt[pos]) lt[pos] = ML==l? l:-1, rt[pos] = MR == r ? r:-1;
 32         else lt[pos] = rt[pos] = -1;
 33         return;
 34     }
 35     int mid = ML + MR >>1;
 36     if(mid >= l) update(l,r,pos<<1,ML,mid,ct);
 37     else chkmax(R,rt[pos<<1]);
 38     if(mid < r) update(l,r,pos<<1|1,mid+1,MR,ct);
 39     else if(lt[pos<<1|1]!=-1) chkmin(L,lt[pos<<1|1]);
 40     upt(pos,ML,MR);
 41 }
 42 // sweep line
 43 ll cal(int len,int m){
 44     if(m>len) return 0;
 45     return len -m + 1;
 46 }
 47 int search(int val,int n){
 48     int l =0, r = n;
 49     while(l<r){
 50         int mid = l + r>>1;
 51         if(X[mid]>=val) r = mid;
 52         else l = mid+1;
 53     }
 54     return l;
 55 }
 56 ll work(){
 57     int len = 0,k = 1;
 58     for(int i=0;i<n;i++){
 59         seg[len] = node(num[i][0],num[i][2],num[i][1]-1,1);
 60         X[len++] = num[i][0];
 61         seg[len] = node(num[i][0],num[i][2],num[i][3],-1);
 62         X[len++] = num[i][2];
 63     }
 64     sort(seg,seg+len);
 65     sort(X,X+len);
 66     for(int i=1;i<len;i++)
 67         if(X[i]!=X[i-1]) X[k++] = X[i];
 68     for(int i=k;i>=1;i--) X[i] = X[i-1];
 69     memset(lt,-1,sizeof(lt));
 70     memset(rt,-1,sizeof(rt));
 71     memset(cnt,0,sizeof(cnt));
 72     X[0] = 0; X[k+1] = w+1;
 73     update(0,0,1,0,k+1,1);
 74     update(k+1,k+1,1,0,k+1,1);
 75     ll last = cal(w,m);
 76     ll ans = last * seg[0].h;
 77     for(int i=0;i<len-1;i++){
 78         int l = search(seg[i].l,k+1);
 79         int r = search(seg[i].r,k+1);
 80         L = w+1, R = -1;
 81         update(l,r,1,0,k+1,seg[i].p);
 82         last -= seg[i].p * cal(X[L]-X[R]-1,m);
 83         last += seg[i].p * cal(X[L]-X[r]-1,m);
 84         last += seg[i].p * cal(X[l]-X[R]-1,m);
 85         ans += last * (seg[i+1].h - seg[i].h);
 86     }
 87     ans += cal(w,m) * (h - seg[len-1].h);
 88     return ans;
 89 }
 90 // main
 91 int main(){
 92     ll ans ;
 93     while(~scanf("%d%d%d%d",&w,&h,&n,&m)){
 94         for(int i=0;i<n;i++) for(int j=0;j<4;j++)
 95             scanf("%d",&num[i][j]);
 96         if(n==0) { 
 97             ans = h*cal(w,m) + w*cal(h,m);
 98             if(m == 1) cout<<ans/2<<endl;
 99             else cout<<ans<<endl;
100             continue;
101         }
102         ans = work();
103         swap(w,h);
104         for(int i=0;i<n;i++){
105             swap(num[i][0],num[i][1]);
106             swap(num[i][2],num[i][3]);
107         }
108         ans += work();
109         if(m==1)
110             cout<<ans/2<<endl;
111         else cout<<ans<<endl;
112     }
113 }
114 
posted on 2012-05-09 22:20 西月弦 阅读(514) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理