正題

---

題目大意

對一個全白矩陣每次選擇一個矩陣顏色取反。

然后求最后所有黑色聯通塊的周長之和。

---

解題思路

因為是算周長，所以我們將一個矩陣拆分成4條邊，然后將橫豎分開處理。

若處理橫的邊，我們按照$x$為關鍵字排序。

然后對于$x$不同的邊分開處理，那么一行最多$N$個點，我們先將這些點離散化。

我們發現一條被覆蓋了奇數次的邊才會被統計入答案，所以我們可以用一個差分數組維護計算一條邊經過了多少次，然后統計答案。

因為總共只有$8?N$個點所以可以過。

時間復雜度$O(NlogN)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=50100; struct line{int x,l,r; }a[2*N],e[2*N]; int num,n,b[2*N],s[2*N],cnt,v[2*N],ans; void addl(int x,int l,int r) {a[num]=(line){x,l,r};} void adde(int x,int l,int r) {e[num]=(line){x,l,r};} bool cmp(line x,line y) {return x.x<y.x;} void work(line *a) {int L=1,R=0;for(R=1;R<=num;){while(a[R].x==a[R+1].x) R++;cnt=0;for(int i=L;i<=R;i++)b[++cnt]=a[i].l,b[++cnt]=a[i].r;sort(b+1,b+1+cnt);cnt=unique(b+1,b+1+cnt)-b-1;for(int i=1;i<=cnt;i++)v[b[i]]=i,s[i]=0;for(int i=L;i<=R;i++)s[v[a[i].l]]++,s[v[a[i].r]]--;for(int i=1;i<=cnt;i++)s[i]+=s[i-1];for(int i=1;i<cnt;i++)ans+=(s[i]&1)*(b[i+1]-b[i]);R++;L=R;} } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x2++,y2++;num++;addl(x1,y1,y2);adde(y2,x1,x2);num++;adde(y1,x1,x2);addl(x2,y1,y2);}sort(a+1,a+1+num,cmp);sort(e+1,e+1+num,cmp);work(a);work(e);printf("%d",ans); }

總結

以上是生活随笔為你收集整理的nssl1351-矩形反色【离散,差分】的全部內容，希望文章能夠幫你解決所遇到的問題。

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