#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, W, H;
vector<int> r, c;
vector<bool> mem;
int ans = 0;
MinSeg scmi, srmi;
MaxSeg scma, srma;
vector<set<int>> byR, byC;
vector<int> fr, fc;
void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
H = h, W = w;
n = H*W;
r = R;
c = C;
if(H <= 1000 && W <= 1000){
byR.resize(H);
byC.resize(W);
fr.assign(H, -1);
fc.assign(W, -1);
for(int i = 0; i < n; i++){
byR[r[i]].insert(i), byC[c[i]].insert(i);
if(fr[r[i]] == -1) fr[r[i]] = i;
if(fc[c[i]] == -1) fc[c[i]] = i;
}
}
else{
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]);
if(H <= 1000 && W <= 1000){
byR[r[a]].erase(b);
byR[r[b]].erase(a);
byR[r[a]].insert(a);
byR[r[b]].insert(b);
byC[c[a]].erase(b);
byC[c[b]].erase(a);
byC[c[a]].insert(a);
byC[c[b]].insert(b);
fr[r[a]] = *byR[r[a]].begin();
fr[r[b]] = *byR[r[b]].begin();
fc[c[a]] = *byC[c[a]].begin();
fc[c[b]] = *byC[c[b]].begin();
vector<int> ncmi(W), ncma(W), nrmi(H), nrma(H);
int val = INF;
for(int i = 0; i < W; i++){
ncmi[i] = val;
val = min(val, fc[i]);
}
val = INF;
for(int i = W-1; i >= 0; i--){
ncma[i] = val;
val = min(val, fc[i]);
}
val = INF;
for(int i = 0; i < H; i++){
nrmi[i] = val;
val = min(val, fr[i]);
}
val = INF;
for(int i = H-1; i >= 0; i--){
nrma[i] = val;
val = min(val, fr[i]);
}
ans = 1;
int cmi = c[0], cma = c[0], rmi = r[0], rma = r[0];
while(true){
int j = min(min(ncmi[cmi], ncma[cma]), min(nrmi[rmi], nrma[rma]));
if(j == INF) break;
cmi = min(cmi, c[j]);
cma = max(cma, c[j]);
rmi = min(rmi, r[j]);
rma = max(rma, r[j]);
int k = min(min(ncmi[cmi], ncma[cma]), min(nrmi[rmi], nrma[rma]));
if(k == INF || (rma-rmi+1)*(cma-cmi+1) == k) ans++;
}
return ans;
}
else{
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 ok = ((cma-cmi+1)*(rma-rmi+1) == i+1);
if(mem[i] && !ok) ans--;
if(!mem[i] && ok) ans++;
mem[i] = ok;
}
return ans;
}
}
