#include "seats.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
int T[1<<21], A[1<<21], cnt[1<<21];
int R[1000010], C[1000010];
int N, M, P;
void init(int rt, int l, int r) {
cnt[rt] = r - l + 1;
if(l == r) return;
int m = (l + r) >> 1;
init(rt<<1, l, m);
init(rt<<1|1, m+1, r);
}
inline void pushup(int rt) {
if(T[rt<<1] == T[rt<<1|1]) cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1], T[rt] = T[rt<<1];
else if(T[rt<<1] < T[rt<<1|1]) cnt[rt] = cnt[rt<<1], T[rt] = T[rt<<1];
else cnt[rt] = cnt[rt<<1|1], T[rt] = T[rt<<1|1];
}
void add(int rt, int l, int r, int s, int e, int c) {
if(s <= l && r <= e) {
T[rt] += c;
A[rt] += c;
return;
}
if(A[rt]) {
T[rt<<1] += A[rt];
A[rt<<1] += A[rt];
T[rt<<1|1] += A[rt];
A[rt<<1|1] += A[rt];
A[rt] = 0;
}
int m = (l + r) >> 1;
if(s <= m) add(rt<<1, l, m, s, e, c);
if(m < e) add(rt<<1|1, m+1, r, s, e, c);
pushup(rt);
}
void add(int l, int r, int v) {
add(1, 1, P, l, r, v);
}
int rval[1000010];
void get_val(int x, int y, int rr[]) {
int rz = 0;
for(int dx : {0,1}) for(int dy : {0,1}) {
int ni = x + dx, nj = y + dy, val = P + 1;
if(1 <= ni && ni <= N && 1 <= nj && nj <= M) {
val = rval[(ni-1)*M+(nj-1)];
}
rr[rz++] = val;
}
sort(rr, rr+4);
}
void give_initial_chart(int H, int W, std::vector<int> tR, std::vector<int> tC) {
N = H; M = W;
P = N * M;
init(1, 1, P);
rep(i, P) R[i + 1] = tR[i] + 1, C[i + 1] = tC[i] + 1;
for(int i=1;i<=P;i++) rval[(R[i]-1)*M+(C[i]-1)] = i;
rep(i, N+1) rep(j, M+1) {
int tt[4];
get_val(i, j, tt);
if(tt[0]<tt[1]) add(tt[0], tt[1]-1, 1);
if(tt[2]<tt[3]) add(tt[2], tt[3]-1, 100);
}
}
void change(int r, int c, int x) {
for(int dx:{-1,0}) for(int dy:{-1,0}) {
int tt[4];
get_val(r+dx, c+dy, tt);
if(tt[0]<tt[1]) add(tt[0], tt[1]-1, -1);
if(tt[2]<tt[3]) add(tt[2], tt[3]-1, -100);
}
rval[(r-1)*M+(c-1)] = x;
for(int dx:{-1,0}) for(int dy:{-1,0}) {
int tt[4];
get_val(r+dx, c+dy, tt);
if(tt[0]<tt[1]) add(tt[0], tt[1]-1, 1);
if(tt[2]<tt[3]) add(tt[2], tt[3]-1, 100);
}
}
int swap_seats(int a, int b) {
++a; ++b;
change(R[a], C[a], b);
change(R[b], C[b], a);
swap(R[a], R[b]);
swap(C[a], C[b]);
return cnt[1];
}
