#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct segment{
vector<int> mn, mx;
void build(int v, int l, int r, vector<int> &vec){
if(r-l == 1){
mn[v] = vec[l], mx[v] = vec[l];
return;
}
int m = (l+r)/2;
build(2*v, l, m, vec);
build(2*v+1, m, r, vec);
mn[v] = min(mn[2*v], mn[2*v+1]);
mx[v] = max(mx[2*v], mx[2*v+1]);
}
segment(){}
segment(int sz, vector<int> &vec){
mn.resize(4*sz, INT_MAX), mx.resize(4*sz, -1);
build(1, 0, sz, vec);
}
void upd(int v, int l, int r, int pos, int val){
if(r-l == 1){
mn[v] = val;
mx[v] = val;
return;
}
int m = (l+r)/2;
if(pos < m) upd(2*v, l, m, pos, val);
else upd(2*v+1, m, r, pos, val);
mn[v] = min(mn[2*v], mn[2*v+1]);
mx[v] = max(mx[2*v], mx[2*v+1]);
}
pair<int,int> query(int v, int l, int r, int ql, int qr){
if(l >= qr or r <= ql) return {INT_MAX, -1};
if(l >= ql and r <= qr) return {mn[v], mx[v]};
int m = (l+r)/2;
auto left = query(2*v, l, m, ql, qr);
auto right = query(2*v+1, m, r, ql, qr);
return {min(left.first, right.first), max(left.second, right.second)};
}
int greater(int v, int l, int r, int ql, int qr, int x){
if(l >= qr or r <= ql) return -1;
if(mx[v] <= x) return -1;
if(r-l == 1) return l;
int m = (l+r)/2;
int y = greater(2*v, l, m, ql, qr, x);
if(y == -1) y = greater(2*v+1, m, r, ql, qr, x);
return y;
}
int smaller(int v, int l, int r, int ql, int qr, int x){
if(l >= qr or r <= ql) return -1;
if(mn[v] >= x) return -1;
if(r-l == 1) return l;
int m = (l+r)/2;
int y = smaller(2*v, l, m, ql, qr, x);
if(y == -1) y = smaller(2*v+1, m, r, ql, qr, x);
return y;
}
};
vector<int> px, py;
set<int> changes;
segment stx, sty;
int h, w;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
for(int i=0; i<H*W; i++) px.push_back(R[i]), py.push_back(C[i]);
h = H, w = W;
stx = segment(h*w, px);
sty = segment(h*w, py);
}
int swap_seats(int a, int b){
swap(px[a], px[b]); swap(py[a], py[b]);
stx.upd(1, 0, h*w, a, px[a]);
sty.upd(1, 0, h*w, a, py[a]);
stx.upd(1, 0, h*w, b, px[b]);
sty.upd(1, 0, h*w, b, py[b]);
vector<int> changes;
int curr = 0;
while(curr != -1){
changes.push_back(curr);
curr = stx.greater(1, 0, h*w, curr+1, h*w, px[curr]);
}
curr = 0;
while(curr != -1){
changes.push_back(curr);
curr = stx.smaller(1, 0, h*w, curr+1, h*w, px[curr]);
}
curr = 0;
while(curr != -1){
changes.push_back(curr);
curr = sty.greater(1, 0, h*w, curr+1, h*w, py[curr]);
}
curr = 0;
while(curr != -1){
changes.push_back(curr);
curr = sty.smaller(1, 0, h*w, curr+1, h*w, py[curr]);
}
sort(changes.begin(), changes.end());
changes.resize(unique(changes.begin(), changes.end())-changes.begin());
assert(changes.size() <= h+w);
int ans = 0;
int prev = -2, prevpos = -1;
for(int x: changes){
if(prev >= prevpos+1 and prev < x+1) ans++;
auto [mnx, mxx] = stx.query(1, 0, h*w, 0, x+1);
auto [mny, mxy] = sty.query(1, 0, h*w, 0, x+1);
prev = (mxx-mnx+1)*(mxy-mny+1);
prevpos = x;
}
if(prev >= prevpos+1) ans++;
return ans;
}
