CF1303F - Number of Components

Solution

思路還是有點妙的。

容易想到并查集，但是并查集不容易維護刪邊，怎么辦呢？

我們考慮拆貢獻，把加邊的貢獻和刪邊的貢獻拆開，分別維護。
只加邊就是四連通加邊，算一下新增多少個連通塊。
只刪邊的貢獻可以從后往前做，變成加邊，對答案的貢獻就是新增連通塊個數的相反數（因為刪邊就是加邊的逆過程，貢獻相反）。

并查集維護即可。

時間復雜度$O(q\log n)$。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-9; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 60; const int mods = 1e9 + 7; const int inv2 = (mods + 1) >> 1; const int MAXN = 100005; const int MAXM = 2000005; const int INF = 0x3f3f3f3f; //1061109567 /*--------------------------------------------------------------------*/namespace FastIO{constexpr int SIZE = (1 << 21) + 1;int num = 0, f;char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)inline void flush() {fwrite(obuf, 1, oS - obuf, stdout);oS = obuf;}inline void putc(char c) {*oS ++ = c;if (oS == oT) flush();}inline void getc(char &c) {for (c = gc(); !isdigit(c) && c != EOF; c = gc());}inline void reads(char *st) {char c;int n = 0;getc(st[++ n]);for (c = gc(); isdigit(c) ; c = gc()) st[++ n] = c;st[n + 1] = '\0';}template<class I>inline void read(I &x) {for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);x *= f;}template<class I>inline void print(I x) {if (x < 0) putc('-'), x = -x;if (!x) putc('0');while (x) que[++ num] = x % 10 + 48, x /= 10;while (num) putc(que[num --]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: putc; using FastIO :: reads; using FastIO :: print;vector<PR> A[MAXM], _A[MAXM]; int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; int f[MAXN], col[305][305], Ans[MAXM], _Ans[MAXM], n, m, Case; int getid(int x, int y) { return (x - 1) * m + y; } int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); } void solve(vector<PR> &A, int opt) {for (auto v : A) f[v.fi] = v.fi;for (auto v : A) {int x = (v.fi - 1) / m + 1, y = (v.fi - 1) % m + 1, t = 1;col[x][y] = 1;for (int i = 0; i < 4 ; ++ i) {int _x = x + dx[i], _y = y + dy[i], p = getid(_x, _y);if (_x < 1 || _y < 1 || _x > n || _y > m || col[x][y] != col[_x][_y] || find(p) == find(v.fi)) continue; f[find(p)] = find(v.fi);-- t;}if (opt == 1) Ans[v.se] += t;else Ans[v.se] -= t;} for (auto v : A) col[(v.fi - 1) / m + 1][(v.fi - 1) % m + 1] = 0; } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifread(n), read(m), read(Case);int MX = max(1000, 2000000 / n / m + 1);for (int i = 1; i <= n * m ; ++ i) A[0].PB(MP(i, 0));for (int i = 1; i <= Case ; ++ i) {int x, y, z;read(x), read(y), read(z);_A[col[x][y]].PB(MP(getid(x, y), i));col[x][y] = z;A[col[x][y]].PB(MP(getid(x, y), i)); }for (int i = 1; i <= n * m ; ++ i) _A[col[(i - 1) / m + 1][(i - 1) % m + 1]].PB(MP(i, Case + 1));for (int i = 0; i <= MX ; ++ i) reverse(_A[i].begin(), _A[i].end());for (int i = 0; i <= MX ; ++ i) solve(A[i], 1);for (int i = 0; i <= MX ; ++ i) solve(_A[i], -1);for (int i = 1; i <= Case ; ++ i) Ans[i] += Ans[i - 1];for (int i = 1; i <= Case; ++ i) print(Ans[i]), putc('\n');return 0; }

總結

以上是生活随笔為你收集整理的CF1303F - Number of Components(并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

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