#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct MinSeg{
vector<int> seg;
int cap;
void init(vector<int> v){
for(cap = 1; cap < (int)v.size(); cap *= 2);
seg.resize(2*cap, INF);
for(int i = 0; i < (int)v.size(); i++) seg[i+cap] = v[i];
for(int i = cap-1; i >= 1; i--) seg[i] = min(seg[2*i], seg[2*i+1]);
}
int qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return seg[i];
if(b < l || r < a) return INF;
int m = (a+b)/2;
return min(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}
int qry(int l, int r){return qry(l, r, 1, cap, 1);}
void upd(int i, int v){
i += cap;
seg[i] = v;
while(i > 1){
i /= 2;
seg[i] = min(seg[2*i], seg[2*i+1]);
}
}
};
struct MaxSeg{
vector<int> seg;
int cap;
void init(vector<int> v){
for(cap = 1; cap < (int)v.size(); cap *= 2);
seg.resize(2*cap, -INF);
for(int i = 0; i < (int)v.size(); i++) seg[i+cap] = v[i];
for(int i = cap-1; i >= 1; i--) seg[i] = max(seg[2*i], seg[2*i+1]);
}
int qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return seg[i];
if(b < l || r < a) return -INF;
int m = (a+b)/2;
return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}
int qry(int l, int r){return qry(l, r, 1, cap, 1);}
void upd(int i, int v){
i += cap;
seg[i] = v;
while(i > 1){
i /= 2;
seg[i] = max(seg[2*i], seg[2*i+1]);
}
}
};
int n;
vector<int> r, c;
vector<bool> mem;
int ans = 0;
MinSeg scmi, srmi;
MaxSeg scma, srma;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
r = R;
c = C;
scmi.init(c);
scma.init(c);
srmi.init(r);
srma.init(r);
mem.resize(n);
int cmi = INF, cma = -INF, rmi = INF, rma = -INF;
for(int i = 0; i < n; i++){
cmi = min(cmi, c[i]);
cma = max(cma, c[i]);
rmi = min(rmi, r[i]);
rma = max(rma, r[i]);
if((cma-cmi+1)*(rma-rmi+1) == i+1) ans++, mem[i] = true;
}
}
int swap_seats(int a, int b) {
if(a > b) swap(a, b);
swap(r[a], r[b]);
swap(c[a], c[b]);
scmi.upd(a, c[a]);
scma.upd(a, c[a]);
srmi.upd(a, r[a]);
srma.upd(a, r[a]);
scmi.upd(b, c[b]);
scma.upd(b, c[b]);
srmi.upd(b, r[b]);
srma.upd(b, r[b]);
int cmi = scmi.qry(1, a), cma = scma.qry(1, a), rmi = srmi.qry(1, a), rma = srma.qry(1, a);
for(int i = a; i < b; i++){
cmi = min(cmi, c[i]);
cma = max(cma, c[i]);
rmi = min(rmi, r[i]);
rma = max(rma, r[i]);
bool b = ((cma-cmi+1)*(rma-rmi+1) == i+1);
if(mem[i] && !b) ans--;
if(!mem[i] && b) ans++;
mem[i] = b;
}
return ans;
}
