#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();
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);
}
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);
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());
}
