#pragma GCC target("avx,avx2,sse,sse2")
#pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; ++i)
struct T {
int mn;
int cnt;
static T mrg(T a, T b){
int mn = min(a.mn, b.mn);
int cnt = (a.mn == mn ? a.cnt : 0) + (b.mn == mn ? b.cnt : 0);
return T{mn,cnt};
}
static T small() { return T{2123123, 0}; }
static T def() { return T{0, 1}; }
};
#define cc(x) complex<int>(x.mn, x.cnt)
struct ST {
int n;
vector<T> v;
vector<int> delta;
void init(int m) {
n = 1;
while(n < m) n *= 2;
v.resize(2*n, T::small());
delta.resize(2*n, 0);
rep(i,0,m) v[i+n] = T::def();
for(int i = n-1; i; --i) v[i] = T::mrg(v[2*i], v[2*i+1]);
}
void push(int t){
if(delta[t] != 0) {
if(t < n) {
delta[2*t+0] += delta[t];
delta[2*t+1] += delta[t];
}
v[t].mn += delta[t];
delta[t] = 0;
}
}
const T& query() {
push(1);
return v[1];
}
const T& upd(int t, int L, int R, int l, int r, int d) {
push(t);
if(l <= L && R <= r) {
delta[t] += d;
push(t);
return v[t];
}
if(r <= L || R <= l) return v[t];
int M = (L+R)/2;
return v[t] = T::mrg(upd(2*t, L, M, l, r, d), upd(2*t+1, M, R, l, r, d));
}
void update(int l, int r, int d){
r = min(n,r);
upd(1, 0, n, l, r, d);
}
};
struct HW {
int n;
vector<int> r, c;
ST st;
int H, W;
int cnt;
bool ini;
set<int> active;
vector<vector<int> > board;
void init(vector<int> r_, vector<int> c_, int H_, int W_){
H = H_;
W = W_;
r = r_;
c = c_;
n = r.size();
st.init(n);
board.resize(H, vector<int>(W));
rep(i,0,n) board[r[i]][c[i]] = i;
rep(x,-1,H) rep(y,-1,W) sqr(x,y,1);
}
int gt(int a, int b){
if(a < 0 || b < 0 || a >= H || b >= W) return 2123123;
else return board[a][b];
}
void sqr(int x, int y, int delta) {
vector<int> all{gt(x,y),gt(x+1,y),gt(x,y+1),gt(x+1,y+1)};
sort(all.begin(),all.end());
vector<pair<int,int> > inv;
int kk = min(gt(x+1,y),gt(x,y+1));
int k0 = gt(x+1,y+1);
if(k0 < kk) st.update(k0, kk, delta);
if(all[2] < n-1) st.update(all[2], all[3], delta);
}
void update(int x, int y, int nw) {
for(int delta : {-1,1}) {
sqr(x-1,y-1,delta);
sqr(x,y-1,delta);
sqr(x-1,y,delta);
sqr(x,y,delta);
board[x][y] = nw;
}
}
int calc() {
T t = st.query();
return t.cnt;
}
int swap(int a, int b){
if(a>b) std::swap(a,b);
update(r[a], c[a], b);
update(r[b], c[b], a);
std::swap(r[a],r[b]);
std::swap(c[a],c[b]);
return calc();
}
} hw;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
hw.init(R,C,H,W);
}
int swap_seats(int a, int b) {
return hw.swap(a,b);
}
