1682E - Unordered Swaps - CodeForces Solution

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
template<class T, class S>
ostream& operator << (ostream &o, const pair<T, S> &p) {
    return o << '(' << p.first << ", " << p.second << ')';
}
template<template<class, class...> class T, class... A>
typename enable_if<!is_same<T<A...>, string>(), ostream&>::type
operator << (ostream &o, T<A...> V) {
	o << '[';
	for(auto a : V) o << a << ", ";
	return o << ']';
}

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;

#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define F(i, l, r) for(ll i = l; i < (r); ++i)
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define P(a, n) { cout << "{ "; F(_, 0, n) cout << a[_] << " "; cout << "}\n"; }
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define K first
#define V second
#define M 1000000007 //998244353
#define N 200010
#define L 20

ll dep[N], par[N][L], p[N];
vl tree[N], path[N];

void dfs(ll i, ll pp) {
    dep[i] = dep[pp] + 1;
    par[i][0] = pp;
    F(l, 1, L) par[i][l] = par[par[i][l - 1]][l - 1];
    for(ll j : tree[i]) if(j - pp) dfs(j, i);
}

ll lca(ll a, ll b) {
    if(dep[a] < dep[b]) swap(a, b);
    FD(l, L - 1, -1) if((dep[a] - dep[b]) >> l) a = par[a][l];
    if(a == b) return a;
    FD(l, L - 1, -1) if(par[a][l] - par[b][l]) a = par[a][l], b = par[b][l];
    return par[a][0];
}

vl getpath(ll a, ll b) {
    ll c = lca(a, b);
    vl va, vb;
    while(a - c) va.push_back(a), a = par[a][0];
    while(b - c) vb.push_back(b), b = par[b][0];
    va.push_back(c);
    reverse(A(vb));
    for(ll x : vb) va.push_back(x);
    va.push_back(0);
    reverse(A(va));
    va.pop_back();
    return va;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    G(n) G(m)
    path[0] = {0};
    F(i, 1, n + 1) cin >> p[i];
    map<pl, ll> swps;
    F(i, 1, m + 1) {
        G(u) G(v)
        tree[u].push_back(v);
        tree[v].push_back(u);
        swps[{u, v}] = swps[{v, u}] = i;
    }
    F(i, 1, n + 1) if(!par[i][0]) dfs(i, i);
    F(i, 1, n + 1) path[p[i]] = getpath(i, p[i]);
    vl nextswaps;
    F(i, 1, n + 1) if(path[p[i]].back() == par[i][0] && path[p[par[i][0]]].back() == i) nextswaps.push_back(i);
    F(i, 0, nextswaps.size()) {
        ll u = nextswaps[i], v = par[u][0];
        cout << swps[{u, v}] << ' ';
        swap(p[u], p[v]);
        path[p[u]].pop_back();
        path[p[v]].pop_back();
        ll nu = path[p[u]].back(), nv = path[p[v]].back();
        if(nu == par[u][0] && path[p[par[u][0]]].back() == u) nextswaps.push_back(u);
        if(nv == par[v][0] && path[p[par[v][0]]].back() == v) nextswaps.push_back(v);
        if(par[nu][0] == u && path[p[nu]].back() == u) nextswaps.push_back(nu);
        if(par[nv][0] == v && path[p[nv]].back() == v) nextswaps.push_back(nv);
    }
}