#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = 5e8;
vector<vector<ll>> vals;
vector<pii> locs;
// pii fz(pii p1, pii p2) {
// if (p1.first<p2.first) {
// return p1;
// }
// if (p2.first<p1.first) {
// return p2;
// }
// assert(p1.first==p2.first);
// return {p1.first,p1.second+p2.second};
// }
// struct Node {
// ll xl=-1; ll xr=-1;
// Node *l=nullptr,*r=nullptr;
// pii val = {INF,-1}; //val, qty: store min value in subtree and multiplicity
// ll lz = 0; //lazy tag: applied to this but not to children
// Node(){};
// Node(ll _xl, ll _xr) {
// xl = _xl; xr = _xr;
// val = {0,xr-xl+1};
// if (xl!=xr) {
// ll xm = (xl+xr)/2;
// l = new Node(xl,xm);
// r = new Node(xm+1,xr);
// }
// }
// void pdn() {
// if (xl==xr) {
// lz=0; return;
// }
// l->val.first += lz;
// l->lz += lz;
// r->val.first += lz;
// r->lz += lz;
// lz = 0;
// }
// void lft() {
// assert(lz==0);
// if (xl==xr) {
// return;
// }
// val = fz(l->val,r->val);
// }
// void appl(ll ql, ll qr, ll v) { //change ql,qr by v
// if (qr<xl || ql>xr) {
// return;
// }
// pdn();
// if (ql<=xl && xr<=qr) {
// val.first+=v;
// lz+=v;
// return;
// }
// assert(xl!=xr);
// l->appl(ql,qr,v);
// r->appl(ql,qr,v);
// lft();
// }
// ll extr() {
// //cout << "val = "<<val.first<<", "<<val.second<<"\n";
// assert(val.first>=4);
// if (val.first==4) {
// return val.second;
// }
// return 0;
// }
// };
// Node* root = new Node();
vector<ll> vf;
void appl(ll a, ll b, ll v) {
for (ll x=a;x<=b;x++) {
vf[x]+=v;
}
}
ll extr() {
ll ans = 0;
for (ll x: vf) {
assert(x>=4);
if (x==4) {
ans++;
}
}
return ans;
}
void prc(ll x, ll y, ll v) { //process square; determine whether to add or subtract
//cout << "prc: x,y="<<x<<","<<y<<"\n";
vector<ll> v0;
v0.push_back(vals[x][y]);
v0.push_back(vals[x][y+1]);
v0.push_back(vals[x+1][y]);
v0.push_back(vals[x+1][y+1]);
sort(v0.begin(),v0.end());
assert(v0[0]<v0[1]);
//cout << "apply add to: "<<v0[0]<<","<<(v0[1]-1)<<"\n";
// root->appl(v0[0],v0[1]-1,v);
appl(v0[0],v0[1]-1,v);
}
void psq(ll x, ll y, ll v) { //center x,y
prc(x-1,y-1,v);
prc(x,y-1,v);
prc(x-1,y,v);
prc(x,y,v);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
//ll vals[H+2][W+2];
vals = vector<vector<ll>> (H+2,vector<ll>(W+2,-1));
for (int h=0;h<(H+2);h++) {
for (int w=0;w<(W+2);w++) {
vals[h][w]=H*W;
}
}
//pii locs[H*W];
ll N = H*W;
locs = vector<pii>(N);
for (ll i=0;i<N;i++) {
locs[i]={R[i]+1,C[i]+1};
vals[R[i]+1][C[i]+1]=i;
}
//root = new Node(0,N-1);
vf = vector<ll>(N,0);
for (ll h=0;h<(H+1);h++) {
for (ll w=0;w<(W+1);w++) {
prc(h,w,1);
}
}
//cout << (root->extr()) <<"=ival\n";
}
int swap_seats(int a, int b) {
psq(locs[a].first,locs[a].second,-1);
psq(locs[b].first,locs[b].second,-1);
swap(locs[a],locs[b]);
vals[locs[a].first][locs[a].second]=a;
vals[locs[b].first][locs[b].second]=b;
psq(locs[a].first,locs[a].second,1);
psq(locs[b].first,locs[b].second,1);
//return (root->extr());
return extr();
}
