Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <bitset>
- #include <vector>
- #include <algorithm>
- #include <random>
- #include <map>
- #include <set>
- #include <deque>
- #include <cassert>
- const int N = 2e6 + 7, A = 26, MOD = 1e9+7, C = 2;
- using namespace std;
- long long n, m;
- struct Query {
- int i, j, i1, j1;
- };
- vector<pair<int, int> > queried, sorted;
- pair<int, int> getCoords(int ind) {
- return { queried[ind].first, queried[ind].second };
- }
- struct dsu {
- int p[N];
- int sz[N];
- int cnt_comps;
- int MinX[N], MaxX[N], MinY[N], MaxY[N];
- long long broken[N];
- bool good[N];
- void build(int n) {
- cnt_comps = 0;
- for (int i = 0; i < n; i++) {
- p[i] = i;
- sz[i] = 1;
- cnt_comps++;
- broken[i] = 0;
- auto c = getCoords(i);
- MinX[i] = c.first;
- MaxX[i] = c.first;
- MaxY[i] = c.second;
- MinY[i] = c.second;
- good[i] = 1;
- }
- }
- int get(int v) {
- if (p[v] == v) {
- return v;
- }
- p[v] = get(p[v]);
- return p[v];
- }
- void merge(int A, int B) {
- int a = get(A);
- int b = get(B);
- if (a == b) {
- broken[a]++;
- long long x = MaxX[a] - MinX[a] + 1;
- long long y = MaxY[a] - MinY[a] + 1;
- long long brk_nd = (x - 1) * y + (y - 1) * x;
- assert(broken[a] <= brk_nd);
- if (broken[a] == brk_nd) {
- cnt_comps++;
- good[a] = 1;
- }
- return;
- }
- if (sz[a] < sz[b]) {
- swap(a, b);
- }
- sz[a] += sz[b];
- p[b] = a;
- if (good[a]) {
- cnt_comps--;
- }
- if (good[b]) {
- cnt_comps--;
- }
- good[a] = 0;
- MinX[a] = min(MinX[a], MinX[b]);
- MinY[a] = min(MinY[a], MinY[b]);
- MaxX[a] = max(MaxX[a], MaxX[b]);
- MaxY[a] = max(MaxY[a], MaxY[b]);
- broken[a] += broken[b] + 1;
- long long x = MaxX[a] - MinX[a] + 1;
- long long y = MaxY[a] - MinY[a] + 1;
- long long brk_nd = (x - 1) * y + (y - 1) * x;
- assert(broken[a] <= brk_nd);
- if (broken[a] == brk_nd) {
- cnt_comps++;
- good[a] = 1;
- }
- }
- };
- dsu D;
- vector<Query> qr;
- int GetInd(int i, int j) {
- pair<int, int> s = { i,j };
- return lower_bound(queried.begin(), queried.end(), s) - queried.begin();
- }
- signed main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #else
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- #endif
- cin >> n >> m;
- int q;
- cin >> q;
- for (int I = 0; I < q; I++) {
- int i1, j1, i2, j2;
- cin >> i1 >> j1 >> i2 >> j2;
- qr.push_back({ i1,j1,i2,j2 });
- sorted.push_back({ i1,j1 });
- sorted.push_back({ i2,j2 });
- }
- sort(sorted.begin(),sorted.end());
- queried.push_back(sorted[0]);
- for (int i = 1; i < sorted.size(); i++) {
- if (sorted[i] != sorted[i - 1]) {
- queried.push_back(sorted[i]);
- }
- }
- long long untouched = ((long long)n) * m;
- untouched -= queried.size();
- D.build(queried.size());
- for (int I = 0; I < q; I++) {
- int i1, j1, i2, j2;
- i1 = qr[I].i;
- j1 = qr[I].j;
- i2 = qr[I].i1;
- j2 = qr[I].j1;
- D.merge(GetInd(i1, j1), GetInd(i2, j2));
- cout << D.cnt_comps + untouched << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement