#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]);
}
}
};
struct RangeSeg{
vector<pair<int, int>> seg;
vector<int> lazy;
int cap;
pair<int, int> combine(pair<int, int> a, pair<int, int> b){
if(a > b) swap(a, b);
if(a.first == b.first) a.second += b.second;
return a;
}
void init(vector<int> v){
int n = (int)v.size();
for(int i = 1; i < n; i++) v[i] += v[i-1];
for(cap = 1; cap < n; cap*=2);
seg.resize(2*cap, {INF, 1});
lazy.resize(2*cap, 0);
for(int i = 0; i < n; i++) seg[i+cap].first = v[i];
for(int i = cap-1; i >= 1; i--) seg[i] = min(seg[2*i], seg[2*i+1]);
}
void apply(int v, int i){
seg[i].first += v;
lazy[i] += v;
}
void push(int i){
apply(lazy[i], 2*i);
apply(lazy[i], 2*i+1);
lazy[i] = 0;
}
void upd(int l, int r, int v, int a, int b, int i){
if(l <= a && b <= r) apply(v, i);
else if(b < l || r < a) return;
else{
push(i);
int m = (a+b)/2;
upd(l, r, v, a, m, 2*i);
upd(l, r, v, m+1, b, 2*i+1);
seg[i] = combine(seg[2*i], seg[2*i+1]);
}
}
void upd(int l, int r, int v){upd(l, r, v, 1, cap, 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;
vector<int> num, adj;
RangeSeg range;
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 if(H == 1){
num.resize(n+2, INF);
adj.resize(n);
for(int i = 0; i < n; i++) num[c[i]+1] = i;
for(int i = 1; i <= n; i++){
adj[num[i]] = 2*(1-(num[i]>num[i-1])-(num[i]>num[i+1]));
}
range.init(adj);
}
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 if(H == 1){
swap(num[c[a]+1], num[c[b]+1]);
auto upd = [&](int i){
if(i == 0 || i == W+1) return;
int x = 2*(1-(num[i]>num[i-1])-(num[i]>num[i+1]));
range.upd(1, num[i], x-adj[num[i]]);
adj[num[i]] = x;
};
upd(c[a]);
upd(c[a]+1);
upd(c[a]+2);
upd(c[b]);
upd(c[b]+1);
upd(c[b]+2);
ans = range.seg[1].second;
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;
}
}
