#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
struct node
{
int mx, cnt;
node()
{
mx = 1e9;
cnt = 0;
}
};
node merge_node(node lf, node rf)
{
node nd;
nd.mx = min(lf.mx, rf.mx);
nd.cnt = 0;
if (lf.mx == nd.mx)
nd.cnt += lf.cnt;
if (rf.mx == nd.mx)
nd.cnt += rf.cnt;
return nd;
}
node tree[4 * maxn];
int lazy[4 * maxn];
void push_lazy(int root, int left, int right)
{
tree[root].mx += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void build(int root, int left, int right)
{
if (left == right)
{
tree[root].cnt = 1;
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
}
void update_range(int root, int left, int right, int qleft, int qright, int val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
int h, w, n;
vector < vector < int > > val;
void change(int x, int y, int k)
{
vector < int > cur;
cur.push_back(val[x][y]);
cur.push_back(val[x][y + 1]);
cur.push_back(val[x + 1][y]);
cur.push_back(val[x + 1][y + 1]);
///cout << "change " << x << " " << y << " " << k << endl;
sort(cur.begin(), cur.end());
update_range(1, 0, n - 1, cur[0], cur[1] - 1, k);
update_range(1, 0, n - 1, cur[2], cur[3] - 1, k);
//cout << cur[0] << " " << cur[1] - 1 << endl;
//cout << cur[2] << " " << cur[3] - 1 << endl;
}
void action_cell(int x, int y, int k)
{
for (int dx = -1; dx <= 0; dx ++)
for (int dy = -1; dy <= 0; dy ++)
{
change(x + dx, y + dy, k);
}
}
vector < int > r, c;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
h = H;
w = W;
n = h * w;
build(1, 0, n - 1);
val.resize(h + 2, vector < int > (w + 2, n));
for (int i = 0; i < n; i ++)
{
val[R[i] + 1][C[i] + 1] = i;
r.push_back(R[i] + 1);
c.push_back(C[i] + 1);
}
for (int i = 0; i <= h; i ++)
for (int j = 0; j <= w; j ++)
change(i, j, 1);
//cout << tree[1].cnt << endl;
//exit(0);
}
int swap_seats(int a, int b)
{
action_cell(r[a], c[a], -1);
action_cell(r[b], c[b], -1);
swap(val[r[a]][c[a]], val[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
action_cell(r[a], c[a], +1);
action_cell(r[b], c[b], +1);
return tree[1].cnt;
}
