題目描述
“為你寫詩，為你靜止，為你做不可能的事”，愛情是一種怪事，它讓奎奎開始學習畫畫。奎奎認為一張畫的藝術價值等于畫上的白色聯通塊個數（當一個格子和它上下左右四個方向上的某個相鄰格子顏色相同，則認為它們屬于同一個聯通塊），奎奎還認為他作畫的藝術價值和妹子對他的好感度緊密相關，因此奎奎非常在意每一時刻他的畫的藝術價值。 為了簡化題目，奎奎在一張n行m列的白色矩形格子畫布上作畫，他一共畫了q筆，每一筆都是從(x1,y1)格子開始到(x2,y2)格子結束(x1=x2或y1=y2)，將所有滿足x1<=x<=x2并且y1<=y<=y2的格子涂黑。奎奎想知道當他畫完每一筆之后，這幅畫的藝術價值是多少。
輸入
第一行三個整數n，m，q (1≤n, m≤1000, 1≤q≤10000 )
下面q行每行4個整數x1，y1，x2，y2 (1≤x1≤x2≤n, 1≤y1≤y2≤m)描述奎奎畫的q條線段的起點和終點
?
輸出
q行，對于奎奎畫的每一條線段，輸出一行一個整數表示該線段畫完之后畫布上白色聯通塊的個數。
樣例輸入 Copy
4 6 5
2 2 2 6
1 3 4 3
2 5 3 5
4 6 4 6
1 6 4 6
樣例輸出 Copy
1
3
3
4
3
比賽的時候還剩二十分鐘開始切這個題，讀完題后的思維跳躍也是一波三折，隊友先是提出二維差分維護(讀錯題了)，被我一口回絕，因為題目要求強制在線，二維差分時間復雜度高達1e10，肯定不行，討論了一小會無果，準備放棄，這時隊友發現了關鍵點，題目給出的每次更新保證了是一個直線，(一開始我也讀錯題了，以為每次需要更新一個子矩陣。。)，這個時候暴力維護的復雜度瞬間下降到了 1e7 ，感覺又變成了一道可以切的題，于是研究如何優化，雖然維護矩陣的復雜度到了1e7，但是維護答案的復雜度仍然是1e10，考慮強制在線的另一種做法就是離線處理，正難則反，不難想到倒著維護，在這個思路的引導向，逐漸想出了正解，也就是并查集維護
題目分析：其實想到并查集倒著維護就比較簡單了，對于每條黑線，我們用maze[ i ][ j ]表示每個點被染成黑色的次數，在讀入數據時，順便將整個矩陣維護為添加了 q 條黑邊后的狀態，此時bfs或dfs找出所有白色的連通塊，并用并查集維護（用搜索找連通塊純粹是因為好寫），然后倒著遍歷每一條黑色的邊，將其還原為白色，對于一條直線上的某個點而言，如果這個點在刪除掉當前黑線后，變為了白色，那么無非只有兩種情況：
當前的點是新出現的一個白色連通塊當前的點和周圍的白色連通塊相連
分類討論一下就好了，注意一下，如果當前點周圍的白色連通塊的數量等于一的話，那么當前點只是單純的和這個白色連通塊連接起來了，對答案沒有影響，如果周圍白色聯通卡的數量大于一的話，那么就將其連到一起了，具體的看代碼實現吧，這一點點邏輯把我繞了有小半個小時
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;const int b[4][2]={0,1,0,-1,1,0,-1,0};int maze[N][N],n,m,k,ans[10100],f[N*N],sum=0;bool vis[N][N];int get_id(int x,int y)
{return (x-1)*m+y-1;
}int find(int x)
{return x==f[x]?x:f[x]=find(f[x]);
}bool merge(int x,int y)
{int xx=find(x);int yy=find(y);if(xx!=yy){f[xx]=yy;return true;}return false;
}void dfs(int x,int y,int sx,int sy)
{merge(get_id(x,y),get_id(sx,sy));vis[x][y]=true;for(int i=0;i<4;i++){int xx=x+b[i][0];int yy=y+b[i][1];if(xx<=0||yy<=0||xx>n||yy>m)continue;if(vis[xx][yy]||maze[xx][yy])continue;dfs(xx,yy,sx,sy);}
}struct Que
{int x1,x2,y1,y2;void input(){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(int i=min(x1,x2);i!=max(x1,x2)+1;i++)for(int j=min(y1,y2);j!=max(y1,y2)+1;j++)maze[i][j]++;}void change(){for(int i=min(x1,x2);i!=max(x1,x2)+1;i++)for(int j=min(y1,y2);j!=max(y1,y2)+1;j++)maze[i][j]--;}void solve(){change();int res=0;//記錄當前直線溝通了多少個連通塊for(int i=min(x1,x2);i!=max(x1,x2)+1;i++)for(int j=min(y1,y2);j!=max(y1,y2)+1;j++){if(maze[i][j])//刪去后仍然為黑色 continue;int cnt=0;//記錄周圍有多少個不同的白色連通塊for(int k=0;k<4;k++){int xx=i+b[k][0];int yy=j+b[k][1];if(xx<=0||yy<=0||xx>n||yy>m)continue;if(maze[xx][yy])continue;if(merge(get_id(i,j),get_id(xx,yy)))cnt++;}if(cnt==0)//新出現的單獨連通塊sum++;else//否則記錄溝通了多少個連通塊res+=cnt-1;}sum-=res;}
}q[10100];void init()
{for(int i=0;i<=get_id(n,m);i++)f[i]=i;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%d%d%d",&n,&m,&k);init();for(int i=1;i<=k;i++)q[i].input();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!vis[i][j]&&!maze[i][j])//找白色連通塊{dfs(i,j,i,j);sum++;}for(int i=k;i>=1;i--)//維護答案{ans[i]=sum;q[i].solve();}for(int i=1;i<=k;i++)printf("%d\n",ans[i]);return 0;
}
?
總結
以上是生活随笔為你收集整理的中石油训练赛 - 奎奎画画(思维+并查集+离线处理)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
