#include "seats.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 1e6 + 10;
vi R, C;
int H, W;
vector<vi> A;
int GetMin(int l1, int r1, int l2, int r2){
int mn = H*W;
for(int i = l1; i < r1; i ++)
for(int j = l2; j < r2; j++)
mn = min(mn, A[i][j]);
return mn;
}
pii BadRange(int i, int j){
vector<pii> V;
V.pb({GetMin(0, i + 1, 0, j + 1), 0});
V.pb({GetMin(0, i + 1, j, W), 1});
V.pb({GetMin(i, H, 0, j + 1), 2});
V.pb({GetMin(i, H, j, W), 3});
sort(all(V));
if(3 - V[0].S == V[1].S) return {V[1].F, A[i][j]};
return {V[2].F, A[i][j]};
}
pii seg[N << 2];
int lz[N << 2];
void Apply(int id, int x){
lz[id] += x;
seg[id].F += x;
}
void Shift(int id){
Apply(id << 1, lz[id]);
Apply(id << 1 | 1, lz[id]);
lz[id] = 0;
}
void Build(int id = 1, int L = 0, int R = H * W){
seg[id] = {0, R - L};
lz[id] = 0;
if(L + 1 == R) return ;
int mid = (L + R) >> 1;
Build(id << 1, L, mid);
Build(id << 1 | 1, mid, R);
}
pii Merge(pii &AA, pii &BB){
if(AA.F != BB.F) return min(AA, BB);
return {AA.F, AA.S + BB.S};
}
int Val[N];
void Add(int id, int l, int r, int x, int L = 0, int R = H * W){
for(int i = l; i < r; i++) Val[i] += x;
return ;
if(r <= L || R <= l) return ;
if(l <= L && R <= r){
Apply(id, x);
return ;
}
Shift(id);
int mid = (L + R) >> 1;
Add(id << 1, l, r, x, L, mid);
Add(id << 1 | 1, l, r, x, mid, R);
seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
return ;
}
int Get0(){
int res = 0;
for(int i = 0; i < H*W; i++){
assert(Val[i] >= 0);
if(Val[i] == 0)
res ++;
}
return res;
}
void AddCell(int i, int j, int z){
pii ran = BadRange(i, j);
//cerr << "! " << i << ' ' << j << " " << ran.F << '\n';
if(ran.F < ran.S)
Add(1, ran.F, ran.S, z);
}
void give_initial_chart(int _H, int _W, vi _R, vi _C){
R = _R; C = _C;
H = _H; W = _W;
A.resize(H, vector<int> (W, 0));
for(int i = 0; i < H * W; i++)
A[R[i]][C[i]] = i;
Build();
for(int i = 0; i < H; i++)
for(int j = 0; j < W; j++)
AddCell(i, j, +1);
//cerr << seg[1].S << ' ' << "#########\n";
}
int swap_seats(int a, int b){
AddCell(R[a], C[a], -1);
AddCell(R[b], C[b], -1);
swap(R[a], R[b]);
swap(C[a], C[b]);
A[R[a]][C[a]] = a;
A[R[b]][C[b]] = b;
AddCell(R[a], C[a], +1);
AddCell(R[b], C[b], +1);
return Get0();
}
