#include "seats.h"
#include <bits/stdc++.h>
#define a first
#define b second
#define mk make_pair
#define pb push_back
#define node pair<pair<int,int>,pair<int,int> >
using namespace std;
const int N = (1e6 + 5);
const int inf = (1e9 + 7);
int n,m;
int r[N],c[N];
int mnx[N],mxx[N],mny[N],mxy[N],d;
node t[N * 4];
bool check (int i) {
int sum = (mxx[i] - mnx[i] + 1) * (mxy[i] - mny[i] + 1);
return (i == sum);
}
node combine(node c,node e) {
c.a.a = max(c.a.a,e.a.a);
c.a.b = min(c.a.b,e.a.b);
c.b.a = max(c.b.a,e.b.a);
c.b.b = min(c.b.b,e.b.b);
return c;
}
void update (int pos,int ca,int cb,int v = 1,int tl = 1,int tr = n * m) {
if (tl == tr) {
t[v].a.a = ca;t[v].a.b = ca;
t[v].b.a = cb;t[v].b.b = cb;
}
else {
int tm = (tl + tr) >> 1;
if (pos <= tm) update (pos,ca,cb,v + v,tl,tm);
else update (pos,ca,cb,v + v + 1,tm + 1,tr);
t[v] = combine(t[v + v],t[v + v + 1]);
}
}
pair<pair<int,int>,pair<int,int> > get(int l,int r,int v = 1,int tl = 1,int tr = n * m) {
if (l > tr || r < tl) return {{0,inf},{0,inf}};
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return combine(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H,m = W;
for (int i = 0; i < R.size(); i ++)
r[i + 1] = R[i],c[i + 1] = C[i];
if (max(n,m) <= 1000) for (int i = 1; i <= n * m; i ++) update(i,r[i],c[i]);
else {
for (int i = 1; i <= n; i ++) {
if (i == 1) {
mxx[i] = r[i];
mnx[i] = r[i];
mxy[i] = c[i];
mny[i] = c[i];
}
else {
mxx[i] = max(mxx[i - 1],r[i]);
mxy[i] = max(mxy[i - 1],c[i]);
mnx[i] = min(mnx[i - 1],r[i]);
mny[i] = min(mny[i - 1],c[i]);
}
d += check(i);
}
}
}
int swap_seats(int a, int b) {
if (max(n,m) <= 1000) {
a ++,b ++;
update(a,r[b],c[b]);
update(b,r[a],c[a]);
swap(r[a],r[b]);
swap(c[a],c[b]);
int i = 2,ans = 1;
while (i <= n * m) {
node cur = get(1,i);
int rs = (cur.a.a - cur.a.b + 1) * (cur.b.a - cur.b.b + 1);
if (rs == i) ans ++;
i = max(rs,i + 1);
}
return ans;
}
else {
a ++,b ++;
if (a > b) swap(a,b);
for (int i = a; i <= b; i ++)
d -= check(i);
swap(r[a],r[b]);
swap(c[a],c[b]);
for (int i = a; i <= b; i ++) {
if (i == 1) {
mxx[i] = r[i];
mnx[i] = r[i];
mxy[i] = c[i];
mny[i] = c[i];
}
else {
mxx[i] = max(mxx[i - 1],r[i]);
mxy[i] = max(mxy[i - 1],c[i]);
mnx[i] = min(mnx[i - 1],r[i]);
mny[i] = min(mny[i - 1],c[i]);
}
d += check(i);
}
return d;
}
}
