#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "sorting.h"
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
const int MAXM = 3 * MAXN;
struct DSU {
int p[MAXN + 10];
int sz[MAXN + 10];
int blk;
vector<pii> hist;
void init(int n) {
// cerr << "dsu init!\n";
memset(p, -1, sizeof(p));
memset(sz, 0, sizeof(sz));
blk = n;
hist.clear();
}
int find(int n) {
if(p[n] < 0) return n;
return find(p[n]);
}
void uni(int a, int b) {
// cerr << "dsu uni " << a << " " << b << "\n";
a = find(a); b = find(b);
if(a == b) {
hist.eb(-1, -1);
return;
}
if(sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b] + 1;
blk--;
hist.eb(a, b);
}
void undo() {
int a, b;
tie(a, b) = hist.back();
hist.pop_back();
if(a < 0) return;
p[b] = -1;
sz[a] -= sz[b] + 1;
blk++;
}
} dsu;
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
vector<pii> ops[MAXM * 4 + 10];
int ans;
void init(int m) {
ans = m + 1;
For(i, 0, MAXM * 4 + 10 - 1) {
ops[i].clear();
}
}
void add(int id, int l, int r, int L, int R, pii p) {
if(l > R || r < L) return;
if(l >= L && r <= R) {
ops[id].eb(p);
return;
}
int m = (l + r) / 2;
if(L <= m) add(L(id), l, m, L, R, p);
if(R > m) add(R(id), m + 1, r, L, R, p);
}
void traverse(int id, int l, int r, int N) {
// cerr << "ops: " << id << " - " << sz(ops[id]) << "\n";
for(auto &p:ops[id]) dsu.uni(p.F, p.S);
if(l == r) {
if(N - dsu.blk <= l) ans = min(ans, l);
// cerr << "traverse: " << l << " " << dsu.blk << "\n";
} else {
int m = (l + r) / 2;
traverse(L(id), l, m, N);
traverse(R(id), m + 1, r, N);
}
For(_, 1, sz(ops[id])) dsu.undo();
}
} seg;
int val[MAXN + 10];
int pos[MAXN + 10];
int last[MAXN + 10];
int tmp[MAXN + 10];
bool check(int n, int lim, vector<pii> &ops) {
For(i, 0, n - 1) tmp[i] = val[i];
ops.clear();
For(i, 0, n - 1) {
while(tmp[i] != i) {
ops.eb(tmp[i], tmp[tmp[i]]);
swap(tmp[i], tmp[tmp[i]]);
}
}
return sz(ops) <= lim;
}
void timer() {
static clock_t lastt = -1;
clock_t cur = clock();
if(lastt != -1) {
cerr << fixed << setprecision(3);
cerr << "elapsed: " << ((double)(cur - lastt) / CLOCKS_PER_SEC) << "\n";
}
lastt = cur;
}
int32_t findSwapPairs(int32_t N, int32_t S[], int32_t M, int32_t X[], int32_t Y[], int32_t P[], int32_t Q[]) {
timer();
For(i, 0, N - 1) {
val[i] = S[i];
pos[val[i]] = i;
}
timer();
// add edges to segment tree
seg.init(M);
memset(last, -1, sizeof(last));
For(i, 0, M - 1) {
int p1 = X[i], p2 = Y[i];
seg.add(0, 0, M, last[p1] + 1, i, pii(p1, val[p1]));
seg.add(0, 0, M, last[p2] + 1, i, pii(p2, val[p2]));
last[p1] = i; last[p2] = i;
swap(pos[val[p1]], pos[val[p2]]);
swap(val[p1], val[p2]);
}
For(i, 0, N - 1) {
seg.add(0, 0, M, last[i] + 1, M, pii(i, val[i]));
}
timer();
// traverse through segment tree
dsu.init(N);
seg.traverse(0, 0, M, N);
timer();
// restore states at time i
For(i, 0, N - 1) {
val[i] = S[i];
pos[val[i]] = i;
}
For(i, 0, seg.ans - 1) {
int p1 = X[i], p2 = Y[i];
swap(pos[val[p1]], pos[val[p2]]);
swap(val[p1], val[p2]);
}
timer();
// construct answer
vector<pii> op;
assert(check(N, seg.ans, op));
while(sz(op) < seg.ans) op.eb(0, 0);
Forr(j, seg.ans - 1, 0) {
int v1 = op[j].F;
int v2 = op[j].S;
P[j] = (int32_t)pos[v1];
Q[j] = (int32_t)pos[v2];
swap(val[pos[v1]], val[pos[v2]]);
swap(pos[v1], pos[v2]);
int p1 = X[j];
int p2 = Y[j];
swap(pos[val[p1]], pos[val[p2]]);
swap(val[p1], val[p2]);
}
timer();
return (int32_t)(seg.ans);
}
/*
30421
10423
10243
*/
