HSGO 2020 PERMSWAP (dsu rollback + Segment Tree)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;
struct dsurollback
{
    int par[N], ans;
    vector<pair<int, int>> snap;
    dsurollback()
    {
        memset(par, -1, sizeof par);
        snap.reserve(N);
        ans = 0;
    }
    int findpar(int v)
    {
        while (par[v] > 0 && (v = par[v]))
            ;
        return v;
    }

    void Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);

        if (u == v)
            return;

        if (par[u] < par[v])
            swap(u, v);

        ++ans;

        snap.emplace_back(u, par[u]);

        par[v] += par[u];
        par[u] = v;
    }

    void rollback(int sz)
    {
        while (sz < (int)snap.size())
        {
            par[par[snap.back().first]] -= snap.back().second;
            par[snap.back().first] = snap.back().second;
            --ans;
            snap.pop_back();
        }
    }
} f;

vector<pair<int, int>> s;
int p[N], a[N];
int n, m;
int x[N], y[N];
vector<int> adj[N * 2];
vector<pair<int, int>> st[N * 2];

void Read()
{
    cin >> n >> m;
    s.reserve(n + m * 2);
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[i];
        s.emplace_back(i, p[i]);
        a[i] = p[i];
    }

    for (int i = 1; i <= m; ++i)
    {
        cin >> x[i] >> y[i];
        if (x[i] != y[i])
        {
            swap(a[x[i]], a[y[i]]);
            s.emplace_back(x[i], a[x[i]]);
            s.emplace_back(y[i], a[y[i]]);
        }
    }
}

#define Find(x, y) (lower_bound(x.begin(), x.end(), y) - x.begin() + 1)

void Update(int id, int l, int r, const int &a, const int &b, const pair<int, int> &x)
{
    if (l > b || r < a)
        return;
    if (l >= a && r <= b)
    {
        st[id].emplace_back(x);
        return;
    }

    Update(id << 1, l, (l + r) / 2, a, b, x);
    Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, x);
}

void DAC(int id, int l, int r)
{
    int shot = f.snap.size();

    for (auto i : st[id])
        f.Merge(i.first, i.second);

    if (l == r)
    {
        cout << f.ans << "\n";
        f.rollback(shot);
        return;
    }

    DAC(id << 1, l, (l + r) / 2);
    DAC(id << 1 | 1, (l + r) / 2 + 1, r);

    f.rollback(shot);
}

void Solve()
{
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());

    for (int i = 1; i <= n; ++i)
    {
        adj[Find(s, make_pair(i, p[i]))].emplace_back(0);
        a[i] = p[i];
    }

    for (int i = 1; i <= m; ++i)
        if (x[i] != y[i])
        {
            adj[Find(s, make_pair(x[i], a[x[i]]))].emplace_back(i);
            adj[Find(s, make_pair(y[i], a[y[i]]))].emplace_back(i);
            swap(a[x[i]], a[y[i]]);
            adj[Find(s, make_pair(x[i], a[x[i]]))].emplace_back(i);
            adj[Find(s, make_pair(y[i], a[y[i]]))].emplace_back(i);
        }

    for (int i = 1; i <= (int)s.size(); ++i)
        for (int j = 0; j < (int)adj[i].size(); j += 2)
            Update(1, 1, m, adj[i][j], (j == ((int)adj[i].size() - 1)) ? m : (adj[i][j + 1] - 1), s[i - 1]);

    DAC(1, 1, m);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}