#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> grid;
vector<int> r,c;
const int SZ = 1<<20;
struct LazyST {
int sz, mn[SZ*2], lz[SZ*2], cnt[SZ*2];
void build(vector<int>& vals, int l, int r, int t = 1) {
if (t == 1) sz = vals.size();
if (r - l == 1) {
mn[t] = vals[l];
cnt[t] = 1;
} else {
int m = l+r>>1;
build(vals, l, m, t*2);
build(vals, m, r, t*2+1);
pull(t);
}
}
void pull(int t) {
mn[t] = min(mn[t*2], mn[t*2+1]);
cnt[t] = 0;
if (mn[t*2] == mn[t]) cnt[t] += cnt[t*2];
if (mn[t*2+1] == mn[t]) cnt[t] += cnt[t*2+1];
}
void push(int t) {
mn[t*2] += lz[t];
mn[t*2+1] += lz[t];
lz[t*2] += lz[t];
lz[t*2+1] += lz[t];
lz[t] = 0;
}
void upd(int ul, int ur, int v, int t, int l, int r) {
if (ur <= l || r <= ul) return;
if (ul <= l && r <= ur) {
mn[t] += v;
lz[t] += v;
return;
}
push(t);
int m = l+r>>1;
upd(ul, ur, v, t*2, l, m);
upd(ul, ur, v, t*2+1, m, r);
pull(t);
}
void upd(int ul, int ur, int v) {upd(ul, ur, v, 1, 0, sz);}
} st;
void upd_sqr(int i, int j, int v) {
vector<int> pts;
for (int ni = 0; ni < 2; ++ni)
for (int nj = 0; nj < 2; ++nj)
pts.push_back(grid[i+ni][j+nj]);
sort(pts.begin(), pts.end());
st.upd(pts[0], pts[1], v);
st.upd(pts[2], pts[3], v);
}
void upd_pt(int i, int j, int v) {
for (auto& [di, dj] : (pair<int,int>[]){{0, 0}, {-1, 0}, {-1, -1}, {0, -1}}) {
upd_sqr(i+di, j+dj, v);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int i: R) r.push_back(i+1);
for (int i: C) c.push_back(i+1);
grid.assign(H+2, vector<int>(W+2, H*W));
for (int i = 0; i < H*W; ++i) {
grid[r[i]][c[i]] = i;
}
vector<int> d(H*W+1), vals(H*W);
for (int i = 0; i <= H; ++i) {
for (int j = 0; j <= W; ++j) {
vector<int> pts;
for (int ni = 0; ni < 2; ++ni)
for (int nj = 0; nj < 2; ++nj)
pts.push_back(grid[i+ni][j+nj]);
sort(pts.begin(), pts.end());
d[pts[0]]++;
d[pts[1]]--;
d[pts[2]]++;
d[pts[3]]--;
}
}
int v = 0;
for (int i = 0; i < H*W; ++i) {
v += d[i];
vals[i] = v;
}
st.build(vals, 0, H*W);
}
int swap_seats(int a, int b) {
upd_pt(r[a], c[a], -1);
upd_pt(r[b], c[b], -1);
swap(grid[r[a]][c[a]], grid[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
upd_pt(r[a], c[a], 1);
upd_pt(r[b], c[b], 1);
return st.cnt[1];
}
