Тир

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
typedef long long ll;
using namespace std;
struct qr {
    int a, b, tp;
};
struct ad {
    int l, r, a, b;
};
vector<int> vec;
vector<pair<int,int>> tree[1600010];
void change(int v, int l, int r, int askl, int askr, int a, int b) {
    if (askr <= l || r <= askl)
        return;
    if (askl <= l && r <= askr) {
        tree[v].push_back({ a,b });
        return;
    }
    int m = (l + r) / 2;
    change(v * 2 + 1, l, m, askl, askr, a, b);
    change(v * 2 + 2, m, r, askl, askr, a, b);
}
vector<int> dsu, cntmish, rang;
void build(int n, int cm) {
    dsu.resize(n);
    cntmish.resize(n);
    rang.resize(n, 1);
    for (int i = 0; i < n; i++)
        dsu[i] = i;
    for (int i = 1; i <= cm; i++)
        cntmish[i] = 1;
}
int Find(int a) {
    return (dsu[a] == a ? a : Find(dsu[a]));
}
struct ch {
    int ind, to, lr, lc;
};
inline ch Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (rang[b] > rang[a])
        swap(a, b);
    dsu[b] = a;
    int lr = rang[a], lc = cntmish[a];
    cntmish[a] += cntmish[b];
    if (rang[b] == rang[a])
        rang[a]++;
    return { b, a, lr, lc };
}
void dfs(int v, int l, int r) {
    vector<ch> changes;
    for (int i = 0; i < tree[v].size(); i++) {
        int a = tree[v][i].first, b = tree[v][i].second;
        a = Find(a), b = Find(b);
        if (a != b) {
            changes.push_back(Union(a, b));
        }
    }
    if (r - l == 1) {
        if (vec[l]) {
            cout << cntmish[Find(0)] << endl;
        }
    }
    else {
        int m = (l + r) / 2;
        dfs(v * 2 + 1, l, m);
        dfs(v * 2 + 2, m, r);
    }
    for (int i = changes.size()-1; i >= 0; i--) {
        cntmish[changes[i].to] = changes[i].lc;
        rang[changes[i].to] = changes[i].lr;
        dsu[changes[i].ind] = changes[i].ind;
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    int tim = 1+m;
    vector<set<pair<int, int>>> rows(n+1), cols(m+1);
    vector<qr> per, qrs;
    for (int i = 1; i <= m; i++) {
        qrs.push_back({ 0,i,0 });
    }
    map<pair<int, int>, int> ma;
    while (q--) {
        int tpp, x, y;
        cin >> tpp >> x >> y;
        if (tpp == 0) {
            int nper = ma[{x, y}];
            int a = per[nper].a, b = per[nper].b, type = per[nper].tp;
            auto ind1 = rows[x].find({ y,nper });
            if (ind1 != rows[x].begin()) {
                auto indl = prev(ind1);
                int fr = a, to = per[indl->second].b;
                qrs.push_back({ min(fr,to), max(fr,to),1 });
            }
            if (next(ind1) != rows[x].end()) {
                auto indr = next(ind1);
                int fr = b, to = per[indr->second].a;
                qrs.push_back({ min(fr, to), max(fr, to), 1 });
            }
            if (ind1 != rows[x].begin() && next(ind1) != rows[x].end()) {
                int fr = per[prev(ind1)->second].b;
                int to = per[next(ind1)->second].a;
                qrs.push_back({ min(fr, to), max(fr, to), 0 });
            }
            auto ind2 = cols[y].find({ x, nper });
            int tp = 0;
            if (ind2 != cols[y].begin()) {
                auto indt = prev(ind2);
                if (per[indt->second].tp == 1)
                    tp = per[indt->second].a;
                else
                    tp = per[indt->second].b;
            }
            int ourtp = b;
            if (type == 2)
                ourtp = a;
            qrs.push_back({ min(tp, ourtp), max(tp, ourtp), 1 });
            int dn = y;
            if (next(ind2) != cols[y].end()) {
                auto indd = next(ind2);
                if (per[indd->second].tp == 1)
                    dn = per[indd->second].b;
                else
                    dn = per[indd->second].a;
            }
            int ourdn = a;
            if (type == 2)
                ourdn = b;
            qrs.push_back({ min(ourdn, dn), max(ourdn, dn), 1 });
            qrs.push_back({ min(tp, dn), max(tp, dn), 0 });
            rows[x].erase({ y, nper });
            cols[y].erase({ x, nper });
        }
        else {
            per.push_back({ tim++, tim++, tpp });
            int a = per.back().a, b = per.back().b;
            rows[x].insert({ y, per.size() - 1 });
            cols[y].insert({ x, per.size() - 1 });
            ma[{x, y}] = per.size() - 1;
            auto ind1 = rows[x].find({ y,per.size()-1 });
            if (ind1 != rows[x].begin() && next(ind1) != rows[x].end()) {
                int fr = per[prev(ind1)->second].b;
                int to = per[next(ind1)->second].a;
                qrs.push_back({ min(fr, to), max(fr, to), 1 });
            }
            if (ind1 != rows[x].begin()) {
                auto indl = prev(ind1);
                int fr = a, to = per[indl->second].b;
                qrs.push_back({ min(fr,to), max(fr, to),0 });
            }
            if (next(ind1) != rows[x].end()) {
                auto indr = next(ind1);
                int fr = b, to = per[indr->second].a;
                qrs.push_back({ min(fr, to), max(fr, to), 0 });
            }
            auto ind2 = cols[y].find({ x, per.size()-1 });
            int tp = 0;
            if (ind2 != cols[y].begin()) {
                auto indt = prev(ind2);
                if (per[indt->second].tp == 1)
                    tp = per[indt->second].a;
                else
                    tp = per[indt->second].b;
            }
            int ourtp = b;
            if (tpp == 2)
                ourtp = a;
            qrs.push_back({ min(tp, ourtp), max(tp, ourtp), 0 });
            int dn = y;
            if (next(ind2) != cols[y].end()) {
                auto indd = next(ind2);
                if (per[indd->second].tp == 1)
                    dn = per[indd->second].b;
                else
                    dn = per[indd->second].a;
            }
            int ourdn = a;
            if (tpp == 2)
                ourdn = b;
            qrs.push_back({ min(ourdn, dn), max(ourdn, dn), 0 });
            qrs.push_back({ min(tp, dn), max(tp, dn), 1 });
        }
        qrs.push_back({ -1,-1, 2 });
    }
    ma.clear();
    vector<ad> edges;
    int ct = 0;
    for (int i = 0; i < qrs.size(); i++) {
        if (qrs[i].tp == 2) {
            if (i != 0)
                vec.push_back(0);
            vec.push_back(1);
            ct += 2;
            continue;
        }
        if (qrs[i].tp == 0)
            ma[{qrs[i].a, qrs[i].b}] = ct;
        else {
            edges.push_back({ ma[{qrs[i].a, qrs[i].b}] , ct, qrs[i].a, qrs[i].b });
            ma.erase({ qrs[i].a, qrs[i].b });
        }
    }
    if (ma.size() > 0)
        vec.push_back(0);
    for (auto pr : ma) {
        edges.push_back({ pr.second, (int)vec.size() - 1, pr.first.first, pr.first.second });
    }
    for (int i = 0; i < edges.size(); i++) {
        change(0, 0, vec.size(), edges[i].l, edges[i].r + 1, edges[i].a, edges[i].b);
    }
    build(tim, m);
    dfs(0, 0, vec.size());
}