#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
#define ll long long
#define para pair<ll, ll>
const int base = 1<<20;
const int MAXN = 1e6+7;
const int INF = 1e9;
para tree[base<<1];
ll lazy[base<<1];
void push(ll v, ll l, ll r){
lazy[l] += lazy[v];
lazy[r] += lazy[v];
tree[l].first += lazy[v];
tree[r].first += lazy[v];
lazy[v] = 0;
}
ll p, k;
ll val;
void build(ll v, ll a, ll b){
if(a == b){
tree[v] = {0, 1};
}
else{
ll mid = (a + b)/2, l = 2*v, r = 2*v+1;
build(l, a, mid);
build(r, mid+1, b);
}
}
void update(ll v, ll a, ll b){
if(a > k || b < p) return;
if(p <= a && k >= b){
tree[v].first += val;
lazy[v] += val;
return;
}
ll mid = (a + b)/2, l = 2*v, r = 2*v+1;
push(v, l, r);
update(l, a, mid);
update(r, mid+1, b);
if(tree[l].first < tree[r].first) tree[v].second = tree[l].second;
else if(tree[l].first > tree[r].first) tree[v].second = tree[r].second;
else tree[v].second = tree[l].second + tree[r].second;
tree[v].first = min(tree[l].first, tree[r].first);
}
para query(ll v, ll a, ll b){
if(a > k || b < p) return {INF, 0};
if(p <= a && k >= b){
return tree[v];
}
ll mid = (a + b)/2, l = 2*v, r = 2*v+1;
push(v, l, r);
para ql = query(l, a, mid);
para qr = query(r, mid+1, b);
if(ql.first < qr.first) return ql;
else if(ql.first > qr.first) return qr;
else return {ql.first, ql.second + qr.second};
}
vector<vector<ll>> grid;
para poz[MAXN];
ll n;
vector<vector<para>> dir = {{{-1, 0}, {-1, -1}, {0, -1}}, {{-1, 0}, {-1, 1}, {0, 1}}, {{0, 1}, {1, 1}, {1, 0}}, {{1, 0}, {1, -1}, {0, -1}}};
void calc(para poz){
for(auto d : dir){
vector<ll> tmp = {grid[poz.first][poz.second]};
for(auto j : d){
tmp.push_back(grid[poz.first+j.first][poz.second+j.second]);
}
sort(tmp.begin(), tmp.end());
// cerr << tmp[0] << "-" << tmp[1]-1 << ", " << tmp[2] << "-" << tmp[3]-1 << "\n";
p = tmp[0], k = tmp[1]-1;
update(1, 1, n+7);
p = tmp[2], k = tmp[3]-1;
update(1, 1, n+7);
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
grid = vector<vector<ll>> (H+2, vector<ll> (W+2, n+1));
build(1, 1, n+7);
for(int i = 0; i < H*W; ++i){
poz[i+1] = {R[i]+1, C[i]+1};
grid[R[i]+1][C[i]+1] = i+1;
}
val = 1;
for(int i = 0; i <= H; ++i){
for(int j = 0; j <= W; ++j){
vector<ll> tmp = {grid[i][j], grid[i+1][j], grid[i][j+1], grid[i+1][j+1]};
sort(tmp.begin(), tmp.end());
p = tmp[0], k = tmp[1]-1;
update(1, 1, n+7);
p = tmp[2], k = tmp[3]-1;
update(1, 1, n+7);
}
}
// for(int i = 1; i <= n; ++i){
// p = k = i;
// cerr << query(1, 1, n+7).first << " ";
// }
// cerr << "\n";
}
int swap_seats(int a, int b){
++a;
++b;
val = -1;
calc(poz[a]);
// for(int i = 1; i <= n; ++i){
// p = k = i;
// cerr << query(1, 1, n+7).first << " ";
// }
// cerr << "\n";
calc(poz[b]);
// for(int i = 1; i <= n; ++i){
// p = k = i;
// cerr << query(1, 1, n+7).first << " ";
// }
// cerr << "\n";
swap(poz[a], poz[b]);
swap(grid[poz[a].first][poz[a].second], grid[poz[b].first][poz[b].second]);
val = 1;
calc(poz[a]);
calc(poz[b]);
// for(int i = 1; i <= n; ++i){
// p = k = i;
// cerr << query(1, 1, n+7).first << " ";
// }
// cerr << "\n";
p = 1, k = n;
return query(1, 1, n+7).second;
}
