#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
struct Node { int mn, mnc; };
struct Segtree {
vector<Node> tree;
vector<int> lazy;
void pull(int idx) {
Node lc = tree[idx*2], rc = tree[idx*2+1];
if(lc.mn < rc.mn) tree[idx] = lc;
if(lc.mn > rc.mn) tree[idx] = rc;
if(lc.mn == rc.mn) tree[idx] = {lc.mn, lc.mnc + rc.mnc};
}
void init(vector<int>& A, int idx, int s, int e) {
if(s == e) {
tree[idx] = {A[s], 1};
return;
}
int m = s+e >> 1;
init(A, idx*2, s, m);
init(A, idx*2+1, m+1, e);
pull(idx);
}
void upd_lazy(int idx, int s, int e) {
if(lazy[idx]) {
tree[idx].mn += lazy[idx];
if(s != e) {
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
}
lazy[idx] = 0;
}
}
void upd(int idx, int s, int e, int l, int r, int y) {
upd_lazy(idx, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r) {
lazy[idx] += y; upd_lazy(idx, s, e);
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, l, r, y);
upd(idx*2+1, m+1, e, l, r, y);
pull(idx);
}
};
const int dx[4] = {0, 0, 1, 1};
const int dy[4] = {0, 1, 0, 1};
int h, w;
Segtree seg;
vector<vector<int> > A;
vector<int> r, c;
pair<pii, pii> ch(int x, int y) {
vector<int> S;
for(int k=0; k<4; k++) S.push_back(A[x + dx[k]][y + dy[k]]);
sort(S.begin(), S.end());
return {{S[0], S[1] - 1}, {S[2], S[3] - 1}};
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
for(auto& it: R) ++it; for(auto& it: C) ++it;
r = R; c = C; h = H; w = W;
vector<int> P(H*W+2, 0);
for(int i=0; i<=H+1; i++) A.push_back(vector<int>(W+2, H*W+1));
for(int i=0; i<H*W; i++) A[R[i]][C[i]] = i+1;
for(int i=0; i<=H; i++) {
for(int j=0; j<=W; j++) {
pii p1, p2; tie(p1, p2) = ch(i, j);
++P[p1.fi]; --P[p1.se + 1];
++P[p2.fi]; --P[p2.se + 1];
}
}
for(int i=1, s=0; i<=H*W; i++) {
s += P[i], P[i] = s;
}
seg.tree.resize(4*H*W); seg.lazy.resize(4*H*W);
seg.init(P, 1, 1, H*W);
}
void update(int x, int y, int d) {
for(int k=0; k<4; k++) {
pii p1, p2; tie(p1, p2) = ch(x-dx[k], y-dy[k]);
seg.upd(1, 1, h*w, p1.fi, p1.se, d);
seg.upd(1, 1, h*w, p2.fi, p2.se, d);
}
}
int swap_seats(int a, int b) {
int ra = r[a], ca = c[a], rb = r[b], cb = c[b];
update(ra, ca, -1); update(rb, cb, -1);
swap(A[ra][ca], A[rb][cb]);
swap(r[a], r[b]); swap(c[a], c[b]);
update(ra, ca, +1); update(rb, cb, +1);
if(seg.tree[1].mn == 4) return seg.tree[1].mnc;
return 0;
}
