//~ #include "seats.h"
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define fort(i,n) for(int i=0;i<=(int)n;++i)
#define fori(i,a,n) for(int i=a;i<(int)n;++i)
#define forit(i,a,n) for(int i=a;i<=(int)n;++i)
#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
using namespace std;
const int INF = 1000005;
struct ST{
struct Node{
int mn=0;
int qt=0;
int lz=0;
};
int n;
vector<Node> st;
void init(int _n){
n=1<<(32-__builtin_clz(_n-1));
st.resize(2*n-1);
fori(i,n-1,2*n-1) st[i].qt = 1;
for(int i=n-2;i>=0;--i) st[i]=merge(st[2*i+1],st[2*i+2]);
}
void push(int i){
if(!st[i].lz) return;
st[i].mn += st[i].lz;
if(i<n-1){
st[2*i+1].lz += st[i].lz;
st[2*i+2].lz += st[i].lz;
}
st[i].lz = 0;
}
Node merge(const Node &a, const Node &b){
if(a.mn < b.mn) return a;
if(b.mn < a.mn) return b;
return {a.mn, a.qt + b.qt, 0};
}
void update(int ul, int ur, int v, int l, int r, int i){
push(i);
if(l>=ur||r<=ul) return;
if(l>=ul&&r<=ur){
st[i].lz += v;
push(i);
return;
}
int m=(l+r)/2;
update(ul,ur,v,l,m,2*i+1);
update(ul,ur,v,m,r,2*i+2);
st[i] = merge(st[2*i+1], st[2*i+2]);
}
void update(int l, int r, int v){
update(l,r,v,0,n,0);
}
Node query(int ql, int qr, int l, int r, int i){
push(i);
if(l>=qr||r<=ql) return {INF, 0, 0};
if(l>=ql&&r<=qr) return st[i];
int m = (l+r)/2;
return merge(query(ql,qr,l,m,2*i+1),query(ql,qr,m,r,2*i+2));
}
int query(int l, int r){
Node aux = query(l,r,0,n,0);
assert(aux.mn == 4);
return aux.qt;
}
void print(ostream &os, int i){
push(i);
if(i>=n-1){
os<<"("<<st[i].mn<<","<<st[i].qt<<") ";
return;
}
print(os,2*i+1);
print(os,2*i+2);
}
void print(ostream &os){
print(os,0);
}
} corners;
ostream &operator<<(ostream &os, ST &st){
st.print(os);
return os;
}
struct P{
int r, c;
};
struct B2{
int a = INF, b = INF;
void add(int x){
if(x < a){
b = a;
a = x;
} else if(x < b){
b = x;
}
}
};
int n;
vector<vector<int>> seats;
vector<P> pos;
void process(int r, int c, int v){
B2 s;
s.add(seats[r][c]);
s.add(seats[r][c+1]);
s.add(seats[r+1][c]);
s.add(seats[r+1][c+1]);
//~ DBG2(s.a, s.b);
corners.update(s.a,s.b,v);
}
void add(int r, int c){
process(r,c,+1);
}
void rem(int r, int c){
process(r,c,-1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H*W;
seats.resize(H+2, vector<int>(W+2,n));
pos.resize(n);
forn(i,n){
int r=R[i]+1;
int c=C[i]+1;
seats[r][c] = i;
pos[i] = {r, c};
}
corners.init(n+1);
fort(i,H) fort(j,W) add(i,j);
//~ DBG(corners);
}
void getAffected(int a, vector<pair<int,int>> &affected){
int r = pos[a].r;
int c = pos[a].c;
forit(i,r-1,r) forit(j,c-1,c) affected.push_back({i,j});
}
int swap_seats(int a, int b) {
vector<pair<int,int>> affected;
getAffected(a, affected);
getAffected(b, affected);
sort(ALL(affected));
affected.resize(unique(ALL(affected))-affected.begin());
for(const auto &x: affected) rem(x.first, x.second);
//~ DBG("remueve");
P &A = pos[a], &B = pos[b];
swap(seats[A.r][A.c], seats[B.r][B.c]);
swap(A,B);
for(const auto &x: affected) add(x.first, x.second);
//~ DBG("agrega");
//~ DBG(corners);
return corners.query(0,n);
}
#ifdef LOCAL
#include "grader.cpp"
#endif
