阳春网站开发,网站建设需要缴纳印花税么,个人网站建立教程,乌克兰武装部队最新战报CF1303F - Number of Components
Solution
思路还是有点妙的。
容易想到并查集#xff0c;但是并查集不容易维护删边#xff0c;怎么办呢#xff1f;
我们考虑拆贡献#xff0c;把加边的贡献和删边的贡献拆开#xff0c;分别维护。 只加边就是四连通加边#xff0c;算…CF1303F - Number of Components
Solution
思路还是有点妙的。
容易想到并查集但是并查集不容易维护删边怎么办呢
我们考虑拆贡献把加边的贡献和删边的贡献拆开分别维护。 只加边就是四连通加边算一下新增多少个连通块。 只删边的贡献可以从后往前做变成加边对答案的贡献就是新增连通块个数的相反数因为删边就是加边的逆过程贡献相反。
并查集维护即可。
时间复杂度O(qlogn)O(q\log n)O(qlogn)。
Code
#include bits/stdc.husing namespace std;templatetypename T inline bool upmin(T x, T y) { return y x ? x y, 1 : 0; }
templatetypename 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 pairint, int PR;
typedef vectorint 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;}templateclass Iinline 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;}templateclass Iinline 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;vectorPR 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(vectorPR 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;
}
