題目鏈接：點擊查看

題目大意：中文題面，簡單明了，不多贅述

題目分析：這個題可以理解為Atlantis的升級版，其實完全可以對Atlantis這道題目的代碼稍加修改就可以交上這個題，關鍵是如何修改？一開始我想用lazy標記將覆蓋的次數下傳，這樣就能讓每個區間都能正確判斷了，可是出現了點小問題就是，如果lazy標記只是標記了，但是卻沒有及時下傳，那么將會無法及時返回正確的覆蓋長度，導致結果錯誤，那么我又想暴力一點，即每次更新區間的覆蓋次數時，不使用lazy標記了，直接更新到葉子節點，完成更新后在上傳更新，這樣還真讓我給過了，一會會放上代碼，就是多了一個pushdown的過程。

但是這樣并不完美，如果這個題想卡我時間，完全可以把我卡死在暴力的這條路上，所以我又去網上搜大牛的題解，發現了一種很巧妙的方法，代替了lazy標記但是卻完成了lazy標記的任務，那就是在線段樹中維護兩個變量，一個是len，表示相應區間被覆蓋大于等于1次的長度，還有一個變量lenlen，表示相應區間被覆蓋大于等于2次的長度，這樣一來，cover變量就會出現三種情況，分別是0,1，大于等于2，下面分情況討論一下

cover大于等于2的時候最簡單，就是該區間已經被覆蓋了兩次及以上，這樣lenlen的長度就便是區間的長度；

在分節點性質討論，若當前節點為葉子節點，當cover為0或1時，因為葉子節點下面沒有可以重疊的區間了，所以lenlen=0；

若當前節點不是葉子節點，當cover為1時，說明當前區間已經被覆蓋過一次了，我們只需要查找子區間內被覆蓋過1次的，取交集便是當前區間覆蓋超過兩次的長度了；

若當前節點不是葉子節點，當cover為0時，說明當前區間沒有被覆蓋過，所以我們只需要查找子區間內被覆蓋超過2次的，取并集便是當前區間覆蓋超過兩次的長度了；

以上就是pushup函數的大體思路了，上代碼對照著看吧：

---

暴力更新：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2100;struct Node {int l,r;double ll,rr,len;int cover,lazy; }tree[N<<2];vector<double>v;struct node {double x,down,up;int into;node(){x=down=up=0;into=0;}bool operator<(node a)const{return x<a.x;} }p[N];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].ll=v[l-1];tree[k].rr=v[r-1];tree[k].len=0;tree[k].cover=0;tree[k].lazy=0;if(l+1==r)return;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid,r); }void pushup(int k) {if(tree[k].cover>1)tree[k].len=tree[k].rr-tree[k].ll;else if(tree[k].l+1==tree[k].r)tree[k].len=0;elsetree[k].len=tree[k<<1].len+tree[k<<1|1].len; }void pushdown(int k,int val)//這里暴力更新到葉子節點 {if(tree[k].l+1==tree[k].r){tree[k].cover+=val;pushup(k);return;}pushdown(k<<1,val);pushdown(k<<1|1,val);pushup(k); }void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){pushdown(k,val);return;}update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;int n;while(w--){scanf("%d",&n);v.clear();for(int i=1;i<=n;i++){double x1,x2,y1,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);p[i].x=x1;p[i+n].x=x2;p[i].up=p[i+n].up=y2;p[i].down=p[i+n].down=y1;p[i].into=1;p[i+n].into=-1;v.push_back(y1);v.push_back(y2);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int len=v.size();sort(p+1,p+2*n+1);build(1,1,len);double ans=0;for(int i=1;i<=2*n;i++){ // cout<<tree[1].len*(p[i].x-p[i-1].x)<<endl;ans+=tree[1].len*(p[i].x-p[i-1].x);int l=lower_bound(v.begin(),v.end(),p[i].down)-v.begin()+1;int r=lower_bound(v.begin(),v.end(),p[i].up)-v.begin()+1;update(1,l,r,p[i].into);}printf("%.2f\n",ans);}return 0; }

成段更新：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2100;struct Node {int l,r;double ll,rr,len,lenlen;int cover; }tree[N<<2];vector<double>v;struct node {double x,down,up;int into;node(){x=down=up=0;into=0;}bool operator<(node a)const{return x<a.x;} }p[N];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].ll=v[l-1];tree[k].rr=v[r-1];tree[k].len=0;tree[k].cover=0;if(l+1==r)return;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid,r); }void pushup(int k) {if(tree[k].cover)//先處理被覆蓋過的區間，只要被覆蓋過了就肯定至少被覆蓋過1次tree[k].len=tree[k].rr-tree[k].ll;else if(tree[k].l+1==tree[k].r)tree[k].len=0;elsetree[k].len=tree[k<<1].len+tree[k<<1|1].len; /***********************************************************************/if(tree[k].cover>1)//再處理被覆蓋過2次的區間，和上面同理tree[k].lenlen=tree[k].rr-tree[k].ll;else if(tree[k].l+1==tree[k].r)tree[k].lenlen=0;else if(tree[k].cover==1)tree[k].lenlen=tree[k<<1].len+tree[k<<1|1].len;elsetree[k].lenlen=tree[k<<1].lenlen+tree[k<<1|1].lenlen; }void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].cover+=val;pushup(k);return;}update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int main() { // freopen("input.txt","r",stdin)int n;int w;cin>>w;while(w--){scanf("%d",&n);v.clear();for(int i=1;i<=n;i++){double x1,x2,y1,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);p[i].x=x1;p[i+n].x=x2;p[i].up=p[i+n].up=y2;p[i].down=p[i+n].down=y1;p[i].into=1;p[i+n].into=-1;v.push_back(y1);v.push_back(y2);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int len=v.size();sort(p+1,p+2*n+1);build(1,1,len);double ans=0;for(int i=1;i<=2*n;i++){ans+=tree[1].lenlen*(p[i].x-p[i-1].x);int l=lower_bound(v.begin(),v.end(),p[i].down)-v.begin()+1;int r=lower_bound(v.begin(),v.end(),p[i].up)-v.begin()+1;update(1,l,r,p[i].into);}printf("%.2f\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 1255 覆盖的面积(线段树+扫描线)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。