1423H - Virus - CodeForces Solution

// clang-format off
#include <bits/stdc++.h>
using namespace std;

// --------------------------- Defines -------------------------------------  //
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<
    typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type
> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef FILE_STREAM
streambuf *cin_backup = cin.rdbuf(), *cout_backup = cout.rdbuf();
ifstream f_in("name.in");
ofstream f_out("name.out");
#endif // FILE_STREAM

#ifdef DEBUG
    #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
    #define dbg(...)
#endif

#define ll long long
#define fill_array(x, y) memset(x, y, sizeof(x))
#define out_range_map(x,y) ((x) < 0 || (y) < 0 || (x) == N || (y) == M)
#define sza(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fori(i, N) for(int i = 0; i < N; i++)
// --------------------------- /Defines/ ------------------------------------ //

class DSURollback {
   public:
    vector<int> parent, rank;
    stack<tuple<int, int, int>> changes;
    int T = 0;

    DSURollback(){};
    DSURollback(int N) { init(N); }

    void init(int N) {
        parent.resize(N);
        rank.resize(N, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) { return parent[u] == u ? u : find(parent[u]); }

    bool union_(int a, int b) {
        a = find(a), b = find(b);
        if (rank[a] < rank[b]) swap(a, b);
        changes.push({b, a, rank[a]});
        if (a == b) return false;
        parent[b] = a;
        rank[a] += rank[b];
        return true;
    }

    void rollback() {
        auto [b, a, ranka] = changes.top();
        changes.pop();
        parent[b] = b;
        rank[a] = ranka;
    }

    bool same_component(int u, int v) { return find(u) == find(v); }
};

class DSUQueueRollback : public DSURollback {
   private:
    typedef struct update {
        int a, b;
        char type;
    };
    vector<update> S;
    int bottom;  // bottom of the stack: S[0..bottom-1] is entirely B's

    inline void advance_bottom() {
        while (bottom < S.size() && S[bottom].type == 'B') bottom++;
    }

    void reverse_updates() {
        fori(i, S.size()) rollback();
        reverse(all(S));
        fori(i, S.size()) {
            DSURollback::union_(S[i].a, S[i].b);
            S[i].type = 'A';
        }
        bottom = 0;
    }

    void fix() {
        if (S.back().type == 'A') return;
        vector<update> saveA, saveB;

        do {
            if (S.back().type == 'A')
                saveA.push_back(S.back());
            else
                saveB.push_back(S.back());
            S.pop_back();
            rollback();
        } while (saveA.size() != saveB.size() && S.size() > bottom);
        reverse(all(saveA));
        reverse(all(saveB));
        for (const update &upd : saveB) union_(upd.a, upd.b, upd.type);
        for (const update &upd : saveA) union_(upd.a, upd.b, upd.type);
    }

   public:
    DSUQueueRollback(int N) : DSURollback(N), bottom(0) {}

    void pop() {
        assert(!S.empty());
        advance_bottom();
        if (bottom == S.size()) reverse_updates();  // No more A's
        fix();
        rollback();
        S.pop_back();
    }

    bool union_(int a, int b, char type = 'B') {
        S.push_back({a, b, type});
        return DSURollback::union_(a, b);
    }
};
// ------------------------- Your code ---------------------------------- //
// clang-format on

void Solve() {
    int n, q, k;
    cin >> n >> q >> k;
    DSUQueueRollback dsu(n + 1);

    int op, x, y, z, day = 0, day_mk = 0;
    vector<vector<pair<int, int>>> contacts(1);

    fori(i, q) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            contacts[day].push_back(make_pair(x, y));
            dsu.union_(x, y);
        } else if (op == 2) {
            cin >> z;
            z = dsu.find(z);
            cout << dsu.rank[z] << "\n";
        } else if (op == 3) {
            day++;
            contacts.push_back(vector<pair<int, int>>());
            if (day_mk + k == day) {
                fori(i, contacts[day_mk].size()) dsu.pop();
                day_mk++;
            }
        }
    }
}

// clang-format off
// --------------------------------------------------------------------- //

int main() {
    #ifdef DEBUG
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #else
        ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int Tc = 1;
    // cin >> Tc;

    fori(i, Tc)
        Solve();

    return 0;
}