#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
const int N = 1e6 + 5;
struct ST{
int tree[N << 2], cnt[N << 2], f[N << 2], a[N];
void build(int l, int r, int x){
if(l == r) { tree[x] = 0, cnt[x] = 1; return; }
int m = (l + r) >> 1;
build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
}
ST(){
build(0, N, 1);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x << 1] += f[x], f[x << 1] += f[x];
tree[x << 1 | 1] += f[x], f[x << 1 | 1] += f[x];
f[x] = 0;
}
void rec(int x){
tree[x] = tree[x << 1], cnt[x] = cnt[x << 1];
if(tree[x << 1] > tree[x << 1 | 1]){
tree[x] = tree[x << 1 | 1], cnt[x] = cnt[x << 1 | 1];
} else if(tree[x << 1] == tree[x << 1 | 1]){
cnt[x] += cnt[x << 1 | 1];
}
}
void add(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l){
return;
}
if(lx >= l && rx <= r){
tree[x] += v, f[x] += v;
return;
}
push(x, lx, rx);
int m = (lx + rx) >> 1;
add(l, r, v, lx, m, x << 1);
add(l, r, v, m + 1, rx, x << 1 | 1);
rec(x);
}
void set(int i, int v){
add(i, N, -a[i] + v, 0, N, 1);
a[i] = v;
}
ar<int, 2> get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return {N, N};
if(lx >= l && rx <= r) return {tree[x], cnt[x]};
push(x, lx, rx);
int m = (lx + rx) >> 1;
auto L = get(l, r, lx, m, x << 1);
auto R = get(l, r, m + 1, rx, x << 1 | 1);
if(L > R) swap(L, R);
if(L[0] == R[0]) L[1] += R[1];
return L;
}
ar<int, 2> get(int l, int r){
return get(l, r, 0, N, 1);
}
}tree;
int n, m, sz;
vector<int> x, y;
vector<vector<int>> a;
int get(int i, int j, int v){
int mask = 0;
if(a[i][j] <= v) mask |= 1;
if(a[i][j + 1] <= v) mask |= 2;
if(a[i + 1][j] <= v) mask |= 4;
if(a[i + 1][j + 1] <= v) mask |= 8;
return mask;
}
int trans(int old, int nw){
if(old == 0){
return 1;
} else if(__builtin_popcount(old) == 1){
if(nw == 6 || nw == 9) return 0;
else return -1;
} else if(__builtin_popcount(old) == 2){
if(old == 6 || old == 9) return 0;
else return 1;
} else {
return -1;
}
}
void rec(int i, int j){
tree.set(a[i][j], trans(get(i - 1, j - 1, a[i][j] - 1), get(i - 1, j - 1, a[i][j])) +
trans(get(i, j - 1, a[i][j] - 1), get(i, j - 1, a[i][j])) +
trans(get(i - 1, j, a[i][j] - 1), get(i - 1, j, a[i][j])) +
trans(get(i, j, a[i][j] - 1), get(i, j, a[i][j])));
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
n = h, m = w;
sz = n * m;
swap(x, r);
swap(y, c);
a.resize(n + 2, vector<int>(m + 2, N));
for(int i=0;i<sz;i++){
x[i]++, y[i]++;
a[x[i]][y[i]] = i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
rec(i, j);
}
}
auto ans = tree.get(0, sz - 1);
assert(ans[0] == 4);
}
int swap_seats(int i, int j){
swap(x[i], x[j]), swap(y[i], y[j]);
a[x[i]][y[i]] = i, a[x[j]][y[j]] = j;
auto check = [&](int x, int y){
return (1 <= x && x <= n && 1 <= y && y <= m);
};
for(int x_ = x[i] - 1; x_ <= x[i] + 1; x_++){
for(int y_ = y[i] - 1; y_ <= y[i] + 1; y_++){
if(check(x_, y_)){
rec(x_, y_);
}
}
}
for(int x_ = x[j] - 1; x_ <= x[j] + 1; x_++){
for(int y_ = y[j] - 1; y_ <= y[j] + 1; y_++){
if(check(x_, y_)){
rec(x_, y_);
}
}
}
auto ans = tree.get(0, sz - 1);
assert(ans[0] == 4);
return ans[1];
}
