沒有傳送門。
不清楚離散化的可以先看看這篇博文：離散化介紹

---

題意

????在2051年，若干火星探險隊探索了這顆紅色行星的不同區域并且制作了這些區域的地圖。現在，Baltic空間機構有一個雄心勃勃的計劃，他們想制作一張整個行星的地圖。為了考慮必要的工作，他們需要知道地圖上已經存在的全部區域的大小。你的任務是寫一個計算這個區域大小的程序。
具體任務要求為：
（1）從輸入中讀取地圖形狀的描述；
（2）計算地圖覆蓋的全部的區域；
（3）輸出探索區域的總面積（即所有矩形的公共面積）。

---

輸入

輸入的第一行包含一個整數n（1≤n≤10000），表示可得到的地圖數目。

以下n行，每行描述一張地圖。每行包含4個整數x1,y1,x2和y2（0≤x1＜x2≤30000,0≤y1＜y2≤30000）。數值（x1,y1）和（x2，y2）是坐標，分別表示繪制區域的左下角和右上角坐標。每張地圖是矩形的，并且它的邊是平行于x坐標軸或y坐標軸的。

---

輸出

輸出文件包含一個整數，表示探索區域的總面積（即所有矩形的公共面積）。

---

題解

????掃描線裸題，線段樹實現。
????面積是二維的，我們選擇一維構造線段樹，另一維按順序不斷掃描即可。

---

代碼

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; typedef long long ll ; const int N=8e4+10;//空間要開夠 不然很容易re和wa int n,ty[N],t[N],tag[N]; ll area=0;struct L{int xa,xb,y;bool up; }l[N];bool cmp(L A,L B){return A.y<B.y; } struct Node{int l,r;int c,width; }e[N];inline int read() {char c=getchar();int x=0;while(c<'0' || c>'9') c=getchar();while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x; }inline void build(int k,int L,int R) {e[k].l=L;e[k].r=R;e[k].c=0;e[k].width=0;if(L+1==R) return;int mid=(L+R)>>1;build(k<<1,L,mid);build(k<<1|1,mid,R);//not-mid+1->false }inline void update(int k) {if(e[k].c>0) {e[k].width=t[e[k].r]-t[e[k].l];}else if(e[k].l+1==e[k].r){e[k].width=0;}else{e[k].width=e[k<<1].width+e[k<<1|1].width;} } inline void add(int k,int L,int R) {if(e[k].l>=L && e[k].r<=R){e[k].c++;update(k);return;}int mid=(e[k].l+e[k].r)>>1;if(L<mid) add(k<<1,L,R);if(R>mid) add(k<<1|1,L,R);update(k); }inline void del(int k,int L,int R) {if(e[k].l>=L && e[k].r<=R){e[k].c--;update(k);return;}int mid=(e[k].l+e[k].r)>>1;if(L<mid) del(k<<1,L,R);if(R>mid) del(k<<1|1,L,R);update(k); }int main(){scanf("%d",&n);for(int i=0;i<n;i++){int a=read(),b=read(),c=read(),d=read();l[i<<1].xa=a;l[i<<1].xb=c;l[i<<1].y=b;l[i<<1].up=true;l[i<<1|1].xa=a;l[i<<1|1].xb=c;l[i<<1|1].y=d;l[i<<1|1].up=false;ty[i<<1]=a;ty[i<<1|1]=c;}n<<=1;sort(l,l+n,cmp);sort(ty,ty+n);int num=0;t[0]=ty[0];for(int i=1;i<n;i++){if(ty[i]!=ty[i-1]){t[++num]=ty[i];}}//離散化 for(int i=0;i<=num;i++) tag[t[i]]=i;build(1,0,num);for(int i=0;i<n-1;i++){//i<n-1 calculate the above partint la=tag[l[i].xa],ra=tag[l[i].xb];if(l[i].up) add(1,la,ra);else del(1,la,ra);area+=e[1].width*(ll)(l[i+1].y-l[i].y);}printf("%lld\n",area);return 0; }

總結

以上是生活随笔為你收集整理的【扫描线】火星探险-线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

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