#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define pb push_back
#define si short int
#define f first
#define s second
#define pill pair<ll, ll>
#define mp make_pair
using namespace std;
const ll N = 4e6 + 1;
const ll big = 1e9;
int n;
int h, w;
int R[N],C[N];
int z[N];
int ans[N];
vector<pair<pill, ll>> q[N];
struct seg {
pair<int,int> t[N];
int u[N];
void push(int v, int l, int r) {
t[v].f += u[v];
if(l != r)u[v * 2] += u[v], u[v * 2 + 1] += u[v];
u[v] = 0;
}
void build(ll v = 1, ll tl = 1, ll tr = n) {
if(tl == tr) {
t[v] = mp(ans[tl], 1);
return;
}
ll m = (tl + tr) >> 1ll;
build(v * 2, tl, m);
build(v * 2 + 1, m + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
if(t[v * 2].f == t[v * 2 + 1].f)
t[v].s = t[v * 2 + 1].s + t[v * 2].s;
}
void upd(ll l, ll r, ll z, ll v = 1, ll tl = 1, ll tr = n) {
push(v, tl, tr);
if(l > tr || tl > r)return;
if(l <= tl && tr <= r)
return (void)(u[v] += z, push(v, tl, tr));
ll m = (tl + tr) >> 1ll;
upd(l, r, z, v * 2, tl, m);
upd(l, r, z, v * 2 + 1, m + 1, tr);
t[v] = min(t[v * 2 + 1], t[v * 2]);
if(t[v * 2 + 1].f == t[v * 2].f)
t[v].s = t[v * 2 + 1].s + t[v * 2].s;
}
} rt;
int get(int x, int y) {
if(x == 0 || y == 0 || x == h + 1 || y == w)
return big;
return z[(x - 1) * w + (y - 1)];
}
void calcfor(ll x, ll y) {
vector<int> z;
z.pb(get(x, y)), z.pb(get(x - 1, y - 1));
z.pb(get(x, y - 1)), z.pb(get(x - 1, y));
sort(z.begin(), z.end());
q[(x - 1) * w + (y - 1)].pb(mp(mp(z[0], min(n, z[1] - 1)), 1));
if(z[2] != big)
q[(x - 1) * w + (y - 1)].pb(mp(mp(z[2], min(n, z[3] - 1)), 1222));
}
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
h = H, w = W + 1;
n = H * W;
for(int i = 0; i < r.size(); i++)
R[i] = r[i], C[i] = c[i], R[i]++, C[i]++, z[(R[i] - 1) * w + (C[i] - 1)] = i + 1;
for(int i = 1; i <= H + 1; i++) {
for(int j = 1; j <= w; j++) {
calcfor(i, j);
for(auto u : q[(i - 1) * w + (j - 1)])
ans[u.f.f] += u.s, ans[u.f.s + 1] -= u.s;
}
}
for(int i = 1; i <= n; i++)
ans[i] += ans[i - 1];
rt.build();
}
int swap_seats(int a, int b) {
vector<pill> x;
x.pb(mp(R[a], C[a])), x.pb(mp(R[b], C[b]));
x.pb(mp(R[a] + 1, C[a])), x.pb(mp(R[b] + 1, C[b]));
x.pb(mp(R[a] + 1, C[a] + 1)), x.pb(mp(R[b] + 1, C[b] + 1));
x.pb(mp(R[a], C[a] + 1)), x.pb(mp(R[b], C[b] + 1));
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
for(auto u : x) {
for(auto v : q[(u.f - 1) * w + (u.s - 1)])
rt.upd(v.f.f, v.f.s, -v.s);
q[(u.f - 1) * w + (u.s - 1)].clear();
}
swap(z[(R[a] - 1) * w + (C[a] - 1)], z[(R[b] - 1) * w + (C[b] - 1)]);
swap(R[a], R[b]), swap(C[a], C[b]);
for(auto u : x) {
calcfor(u.f, u.s);
for(auto v : q[(u.f - 1) * w + (u.s - 1)])
rt.upd(v.f.f, v.f.s, v.s);
}
rt.push(1, 1, n);
return rt.t[1].s;
}
/*
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<int> rr, cc;
for(int i = 1, a, b; i <= n*m; i++)
cin >> a >> b, rr.pb(a), cc.pb(b);
give_initial_chart(n, m, rr, cc);
while(q--) {
ll a, b;
cin >> a >> b;
cout << swap_seats(a, b) << "\n";
}
} */
