#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct bit {
vector<int> tree;
void init(int n) {
tree.assign(n + 1, 0);
}
void upd(int n, int x) {
for (int i = n + 1; i < tree.size(); i += i & -i) tree[i] += x;
}
int ask(int n, int res = 0) {
for (int i = n + 1; i > 0; i -= i & -i) res += tree[i];
return res;
}
} solver;
int H, W;
vector<int> R, C;
vector<int> special_grid;
vector<pair<int, int>> updates;
vector<vector<int>> grid;
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
H = h, W = w;
R = r, C = c;
special_grid.resize(H * W);
solver.init(H * W);
grid.assign(H, vector<int>(W, -1));
for (int i = 0; i < H * W; i++) {
if (i > 0) special_grid[i] = special_grid[i - 1];
grid[R[i]][C[i]] = i;
if (C[i] == 0 || grid[R[i]][C[i] - 1] == -1) special_grid[i]++;
if (C[i] > 0 && grid[R[i]][C[i] - 1] != -1) special_grid[i]--;
if (C[i] == W - 1 || grid[R[i]][C[i] + 1] == -1) special_grid[i]++;
if (C[i] < W - 1 && grid[R[i]][C[i] + 1] != -1) special_grid[i]--;
}
for (int i = 0; i < H * W; i++) {
if (special_grid[i] == 2) solver.upd(i, 1);
}
}
int swap_seats(int a, int b) {
int leftA, rightA, leftB, rightB, A, B;
leftA = (C[a] > 0)? grid[R[a]][C[a] - 1] : 1e8;
rightA = (C[a] < W - 1)? grid[R[a]][C[a] + 1] : 1e8;
leftB = (C[b] > 0)? grid[R[b]][C[b] - 1] : 1e8;
rightB = (C[b] < W - 1)? grid[R[b]][C[b] + 1] : 1e8;
A = grid[R[a]][C[a]];
B = grid[R[b]][C[b]];
int updA = 0, updLA = 0, updRA = 0, updB = 0, updLB = 0, updRB = 0;
if (leftA > A) updLA++;
if (rightA > A) updRA++;
if (leftA > B) updLA--;
if (rightA > B) updRA--;
if (leftB > B) updLB++;
if (rightB > B) updRB++;
if (leftB > A) updLB--;
if (rightB > A) updRB--;
if (A > leftA) updA++;
if (A > rightA) updA++;
if (A > leftB) updA--;
if (A > rightB) updA--;
if (B > leftB) updB++;
if (B > rightB) updB++;
if (B > leftA) updB--;
if (B > rightA) updB--;
if (special_grid[leftA] == 2 && special_grid[leftA] + updLA != 2) {
solver.upd(leftA, -1);
} else if (special_grid[leftA] != 2 && special_grid[leftA] + updLA == 2) {
solver.upd(leftA, +1);
}
special_grid[leftA] += updLA;
if (special_grid[rightA] == 2 && special_grid[rightA] + updRA != 2) {
solver.upd(rightA, -1);
} else if (special_grid[rightA] != 2 && special_grid[rightA] + updRA == 2) {
solver.upd(rightA, +1);
}
special_grid[rightA] += updRA;
if (special_grid[leftB] == 2 && special_grid[leftB] + updLB != 2) {
solver.upd(leftB, -1);
} else if (special_grid[leftB] != 2 && special_grid[leftB] + updLB == 2) {
solver.upd(leftB, +1);
}
special_grid[leftB] += updLB;
if (special_grid[rightB] == 2 && special_grid[rightB] + updRB != 2) {
solver.upd(rightB, -1);
} else if (special_grid[rightB] != 2 && special_grid[rightB] + updRB == 2) {
solver.upd(rightB, +1);
}
special_grid[rightB] += updRB;
swap(R[a], R[b]);
swap(C[a], C[b]);
return solver.ask(H * W - 1);
}
