#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T, int DEF=0>
class Seg {
public:
vi SEG;
int sz;
T t;
void resize(int _sz) {
sz = _sz;
SEG.resize(sz*4);
}
void build(int p=0, int l=0, int r=-1) {
if(r == -1) r = sz-1;
if(l == r) {
SEG[p] = 0;
return;
}
int m=(l+r)/2;
build(p*2+1,l,m);
build(p*2+2,m+1,r);
if(t(SEG[p*2+1], SEG[p*2+2])) SEG[p] = SEG[p*2+1];
else SEG[p] = SEG[p*2+2];
}
int get(int i, int j, int p=0, int l=0, int r=-1) {
if(r == -1) r = sz-1;
if(j < l || i > r) return DEF;
if(i <= l && j >= r) return SEG[p];
int m=(l+r)/2;
int a=get(i,j,p*2+1,l,m);
int b=get(i,j,p*2+2,m+1,r);
if(t(a,b)) return a;
else return b;
}
void set(int i, int x, int p=0, int l=0, int r=-1) {
if(r == -1) r = sz-1;
if(i < l || i > r) return;
if(l == r) {
SEG[p] = x;
return;
}
int m=(l+r)/2;
set(i,x,p*2+1,l,m);
set(i,x,p*2+2,m+1,r);
if(t(SEG[p*2+1], SEG[p*2+2])) SEG[p] = SEG[p*2+1];
else SEG[p] = SEG[p*2+2];
}
};
int h, w, n;
vi r, c;
vector<Seg<greater<int>>> maxR;
vector<Seg<greater<int>>> maxC;
int tot=0;
vi mnR, mxR, mnC, mxC;
vi A;
vi added;
vi SEG, SEGMIN, SEGCNT;
void updateNode(int p) {
SEG[p] = 0;
SEGMIN[p] = min(SEGMIN[p*2+1], SEGMIN[p*2+2]);
SEGCNT[p] = 0;
if(SEGMIN[p*2+1] == SEGMIN[p]) SEGCNT[p] += SEGCNT[p*2+1];
if(SEGMIN[p*2+2] == SEGMIN[p]) SEGCNT[p] += SEGCNT[p*2+2];
}
void buildSeg(int p=0, int L=0, int R=n-1) {
if(L == R) {
SEG[p] = 0;
SEGMIN[p] = 0;
SEGCNT[p] = 1;
return;
}
int m=(L+R)/2;
buildSeg(p*2+1,L,m);
buildSeg(p*2+2,m+1,R);
updateNode(p);
}
void addSeg(int i, int j, int x, int lazy=0, int p=0, int L=0, int R=n-1) {
SEG [p] += lazy;
SEGMIN[p] += lazy;
if(j < L || i > R) return;
if(i <= L && j >= R) {
SEG [p] += x;
SEGMIN[p] += x;
return;
}
int m=(L+R)/2;
addSeg(i,j,x,SEG[p],p*2+1,L,m);
addSeg(i,j,x,SEG[p],p*2+2,m+1,R);
updateNode(p);
}
void updateNeigbours(int i, int j, int x=1) {
if(i < 0 || i >= n) return;
int bg = A[i], ed;
if(j < 0 || j >= n) {
ed = n-1;// always empty
} else {
ed = A[j]-1;
}
if(ed < bg) return;
addSeg(bg, ed, x);
}
void updateRange(int L, int R) {
REI(i,L,R) {
if(added[i]) tot--;
added[i] = 0;
mnR[i] = r[i];
mxR[i] = r[i];
mnC[i] = c[i];
mxC[i] = c[i];
if(i != 0) {
mnR[i] = min(mnR[i], mnR[i-1]);
mxR[i] = max(mxR[i], mxR[i-1]);
mnC[i] = min(mnC[i], mnC[i-1]);
mxC[i] = max(mxC[i], mxC[i-1]);
}
if((mxR[i]-mnR[i]+1)*(mxC[i]-mnC[i]+1) == i+1) {
tot++;
added[i] = 1;
}
}
}
void give_initial_chart(int H, int W, vi R, vi C) {
h=H, w=W, r=R, c=C;
n = h*w;
maxR.resize(h);
maxC.resize(w);
RE(i,h) maxR[i].resize(w);
RE(i,w) maxC[i].resize(h);
RE(i,n) maxR[r[i]].set(c[i],i);
RE(i,n) maxC[c[i]].set(r[i],i);
mnR .assign(n, INF);
mxR .assign(n, -INF);
mnC .assign(n, INF);
mxC .assign(n, -INF);
added.assign(n, 0);
updateRange(0,n-1);
if(h == 1) {
SEG .resize(n*4);
SEGMIN.resize(n*4);
SEGCNT.resize(n*4);
A.resize(n);
RE(i,n) A[c[i]] = i;
buildSeg();
RE(i,n) updateNeigbours(i,i+1), updateNeigbours(i,i-1);
}
}
int swap_seats_1(int a, int b);
int swap_seats(int a, int b) {
if(h == 1) return swap_seats_1(a, b);
if(b < a) swap(a,b);
swap(r[a], r[b]);
swap(c[a], c[b]);
if(h > 1000 || w > 1000) {
updateRange(a,b);
return tot;
}
maxR[r[a]].set(c[a],a);
maxR[r[b]].set(c[b],b);
maxC[c[a]].set(r[a],a);
maxC[c[b]].set(r[b],b);
int cnt = 0;
int cMinR = r[0];
int cMaxR = r[0];
int cMinC = c[0];
int cMaxC = c[0];
int i = 0;
while(1) {
if(i == (cMaxR-cMinR+1)*(cMaxC-cMinC+1)-1) cnt++;
int val[4], res=0;
val[0] = (cMinR == 0 ? INF : maxR[cMinR-1].get(cMinC, cMaxC));
val[1] = (cMinC == 0 ? INF : maxC[cMinC-1].get(cMinR, cMaxR));
val[2] = (cMaxR == h-1 ? INF : maxR[cMaxR+1].get(cMinC, cMaxC));
val[3] = (cMaxC == w-1 ? INF : maxC[cMaxC+1].get(cMinR, cMaxR));
RE(i,4) if(val[i] < val[res]) res = i;
if(val[res] == INF) break;
if(res == 0) cMinR--;
if(res == 1) cMinC--;
if(res == 2) cMaxR++;
if(res == 3) cMaxC++;
i = max(i, val[res]);
}
return cnt;
}
int swap_seats_1(int a, int b) {
set<ii> updatedNeigbours;
updatedNeigbours.insert({c[a] ,c[a]+1});
updatedNeigbours.insert({c[a] ,c[a]-1});
updatedNeigbours.insert({c[a]-1,c[a] });
updatedNeigbours.insert({c[a]+1,c[a] });
updatedNeigbours.insert({c[b] ,c[b]+1});
updatedNeigbours.insert({c[b] ,c[b]-1});
updatedNeigbours.insert({c[b]-1,c[b] });
updatedNeigbours.insert({c[b]+1,c[b] });
for(ii p : updatedNeigbours) updateNeigbours(p.fi, p.se, -1);
swap(r[a], r[b]);
swap(c[a], c[b]);
A[c[a]] = a;
A[c[b]] = b;
for(ii p : updatedNeigbours) updateNeigbours(p.fi, p.se, 1);
if(SEGMIN[0] != 2) return 0;
else return SEGCNT[0];
}
