#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int INF = 1e9;
pii comb(pii a, pii b){
return {max(a.first,b.first), min(a.second,b.second)};
}
struct SegmentTree{
vector<pii> S;
int len = 1;
SegmentTree(vector<int> arr){
int n = arr.size();
while (len < n) len <<= 1;
S.resize(2 * len);
for(int i = 0; i < n; i++){
S[i+len] = {arr[i],arr[i]};
}
for(int i = len-1; i > 0; i--){
S[i] = comb(S[i*2],S[i*2+1]);
}
}
void upd(int i, int v) {
i += len;
S[i] = {v,v};
for (i /= 2; i > 0; i /= 2){
S[i] = comb(S[i*2],S[i*2+1]);
}
}
pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if (r == -2) r = len;
if (ql <= l && r <= qr) return S[i];
if (r <= ql || qr <= l) return {-INF,INF};
int mid = (l + r) / 2;
return comb(query(ql, qr, l, mid, i * 2), query(ql, qr, mid, r, i * 2 + 1));
}
};
vector<int> r, c;
vector<int> ans;
int h, w;
int n;
int res = 0;
void give_initial_chart(int Hi, int Wi, std::vector<int> R, std::vector<int> C){
r = R;
c = C;
h = Hi;
w = Wi;
n = h * w;
ans.resize(n);
SegmentTree segC(r);
SegmentTree segR(c);
for(int i = 0; i < n; i++){
pii cans = segC.query(0,i+1);
pii rans = segR.query(0,i+1);
int ws = cans.first-cans.second+1;
int hs = rans.first-rans.second+1;
ans[i] = (ws*hs) == (i+1);
res += ans[i];
}
}
int swap_seats(int a, int b){
swap(c[a], c[b]);
swap(r[a], r[b]);
SegmentTree segC(r);
SegmentTree segR(c);
int nextCheck = 0;
for (int i = 0; i < n; i=max(nextCheck-50,i+1)){
pii cans = segC.query(0,i+1);
pii rans = segR.query(0,i+1);
int ws = cans.first-cans.second+1;
int hs = rans.first-rans.second+1;
res-=ans[i];
nextCheck = (ws*hs)-1;
ans[i] = (ws*hs) == (i+1);
res += ans[i];
}
return res;
}
