#include "seats.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define all(a) begin(a), end(a)
struct SqrtDec {
static constexpr int BLK = 1024;
struct T {
// vector<int> cnt;
map<int, int> cnt;
array<int, BLK> a;
int lazy = 0;
// T(int max_val) : cnt(max_val * 2 + 1), lazy(max_val) {}
T() {
fill(all(a), 0);
cnt[0] = BLK;
}
void add(int d) { lazy += d; }
void add(int i, int d) {
--cnt[a[i]];
++cnt[a[i] += d];
}
int get(int x) { return cnt[x - lazy]; }
int get(int i, int d) { return a[i] + lazy == d; }
int gv(int i) { return a[i] + lazy; }
};
vector<T> blocks;
// SqrtDec(int n, int mx) : blocks(n, T(mx)) {}
void init(vector<int> a) {
// assert(*max_element(all(a)) <= mx && *min_element(all(a)) >= 0);
blocks.assign((a.size() + BLK - 1) / BLK, T{});
for (int i = 0; i < a.size(); i++) {
blocks[i / BLK].add(i % BLK, a[i]);
}
}
void add(int l, int r, int d) {
while (l % BLK && l <= r) {
blocks[l / BLK].add(l % BLK, d);
l++;
}
while (l + BLK <= r) {
blocks[l / BLK].add(d);
l += BLK;
}
while (l <= r) {
blocks[l / BLK].add(l % BLK, d);
l++;
}
}
int get(int l, int r, int x) {
int res = 0;
while (l % BLK && l <= r) {
res += blocks[l / BLK].get(l % BLK, x);
l++;
}
while (l + BLK <= r) {
res += blocks[l / BLK].get(x);
l += BLK;
}
while (l <= r) {
res += blocks[l / BLK].get(l % BLK, x);
l++;
}
return res;
}
void print(int l, int r) {
while (l <= r) {
cerr << blocks[l / BLK].gv(l % BLK) << " ";
l++;
}
cerr << "\n";
}
};
int SZ;
SqrtDec sqdec;
vector<pair<int, int>> pos;
vector<vector<int>> index;
int get_delta(int neig) {
if (neig == 2) {
return -1;
} else if (neig == 0) {
return +1;
}
return 0;
}
int get_neig(pair<int, int> p, int t) {
auto [y, x] = p;
assert(y == 0);
int neig = 0;
if (x > 0) {
neig += index[y][x - 1] <= t;
}
if (x + 1 < index[0].size()) {
neig += index[y][x + 1] <= t;
}
return neig;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
assert(H == 1);
SZ = H * W;
index.assign(H, vector<int>(W, H * W));
vector<int> cnt(SZ);
int bords = 0;
for (int i = 0; i < SZ; i++) {
int y = R[i], x = C[i];
pos.push_back({y, x});
int neig = get_neig({y, x}, i);
bords += get_delta(neig);
cnt[i] = bords;
index[y][x] = i;
}
sqdec.init(cnt);
// sqdec.print(0, SZ - 1);
}
void unroll(pair<int, int> p) {
auto [y, x] = p;
vector<int> ts{index[y][x]};
if (x >= 1) {
ts.push_back(index[y][x - 1]);
}
if (x + 1 < index[0].size()) {
ts.push_back(index[y][x + 1]);
}
for (auto t : ts) {
auto p = pos[t];
sqdec.add(t, SZ - 1, -get_neig(p, t));
}
index[y][x] = SZ;
}
void roll(pair<int, int> p, int val) {
auto [y, x] = p;
index[y][x] = val;
vector<int> ts{index[y][x]};
if (x >= 1) {
ts.push_back(index[y][x - 1]);
}
if (x + 1 < index[0].size()) {
ts.push_back(index[y][x + 1]);
}
for (auto t : ts) {
auto p = pos[t];
sqdec.add(t, SZ - 1, get_neig(p, t));
}
}
void remove(pair<int, int> p) {
unroll(p);
roll(p, SZ);
}
void add(pair<int, int> p, int t) {
unroll(p);
roll(p, t);
}
int swap_seats(int a, int b) {
assert(a != b);
auto &pa = pos[a], &pb = pos[b];
remove(pa);
remove(pb);
swap(pa, pb);
// sqdec.print(0, SZ - 1);
add(pa, a);
add(pb, b);
// cerr << "Index: ";
// for (auto i : index[0]) {
// cerr << i << " ";
// }
// cerr << "\n";
// sqdec.print(0, SZ - 1);
return sqdec.get(0, SZ - 1, 1);
}
