#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e6+5;
int N, h, w, r[nx], c[nx], dp[nx], tmp[5][5], mp[5][5], dx[]={-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[]={-1, 0, 1, -1, 0, 1, -1, 0, 1};
vector<vector<int>> v;
struct segtree
{
struct node
{
int mn, f, lz;
} d[4*nx];
node merge(node a, node b)
{
if (a.mn==b.mn) a.f+=b.f;
if (a.mn<=b.mn) return a;
else return b;
}
void pushlz(int l, int r, int i)
{
if (l==r) return d[i].mn+=d[i].lz, d[i].lz=0, void();
d[2*i].lz+=d[i].lz;
d[2*i+1].lz+=d[i].lz;
d[i].mn+=d[i].lz;
d[i].lz=0;
}
void build(int l, int r, int i)
{
if (l==r) return void(d[i].f=1);
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=merge(d[2*i], d[2*i+1]);
}
void update(int l, int r, int i, int ql, int qr, int vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return d[i].lz=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql, qr, vl);
d[i]=merge(d[2*i], d[2*i+1]);
}
} s;
int solve()
{
int cnt=0;
for (int i=0; i<5; i++) for (int j=0; j<5; j++) tmp[i][j]=0;
for (int i=1; i<=4; i++) for (int j=1; j<=3; j++) if (mp[i][j]+mp[i-1][j]==1) tmp[i][j]=1;
for (int i=1; i<=4; i++) for (int j=1; j<=3; j++) cnt+=(tmp[i][j]&&(!tmp[i][j-1]));
for (int i=0; i<5; i++) for (int j=0; j<5; j++) tmp[i][j]=0;
for (int i=1; i<=3; i++) for (int j=1; j<=4; j++) if (mp[i][j]+mp[i][j-1]==1) tmp[i][j]=1;
for (int i=1; i<=3; i++) for (int j=1; j<=4; j++) cnt+=(tmp[i][j]&&(!tmp[i-1][j]));
return cnt;
}
void precompute()
{
for (int i=0; i<(1<<9); i++)
{
if (i&(1<<4)) continue;
for (int j=0; j<9; j++) mp[j/3+1][(j%3)+1]=(i&(1<<j))>0;
dp[i]=-solve();
mp[2][2]=1;
dp[i]+=solve();
}
}
void updateseats(int x, int y, int mul)
{
if (x==0||x==h+1||y==0||y==w+1) return;
int c=0;
for (int i=0; i<9; i++) if (i!=4&&v[x+dx[i]][y+dy[i]]<v[x][y]) c|=(1<<i);
s.update(1, N, 1, v[x][y], N, mul*dp[c]);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h=H; w=W; N=h*w;
v.resize(h+2);
for (int i=0; i<h+2; i++) v[i].resize(w+2);
for (int i=0; i<h+2; i++) for (int j=0; j<w+2; j++) v[i][j]=1e9;
for (int i=1; i<=N; i++) r[i]=R[i-1]+1;
for (int i=1; i<=N; i++) c[i]=C[i-1]+1;
for (int i=1; i<=N; i++) v[r[i]][c[i]]=i;
s.build(1, N, 1);
precompute();
for (int i=1; i<=N; i++) updateseats(r[i], c[i], 1);
}
int swap_seats(int a, int b) {
a++; b++;
set<pair<int, int>> upd;
for (int i=-1; i<=1; i++) for (int j=-1; j<=1; j++) upd.insert({r[a]+i, c[a]+j}), upd.insert({r[b]+i, c[b]+j});
for (auto [x, y]:upd) updateseats(x, y, -1);
swap(v[r[a]][c[a]], v[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for (auto [x, y]:upd) updateseats(x, y, 1);
return s.d[1].f;
}
