#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> a;
vector<pair<int, int>> b;
template <typename F>
struct SegmentTree2D
{
int n, m, init, to;
vector<vector<int>> seg;
vector<vector<int>> a;
F func;
void build(int tr, int dr, int lc, int rc, int t1, int t2)
{
if(tr == dr)
{
if(lc == rc)
{
seg[t1][t2] = a[tr][lc];
return;
}
int md = (lc + rc) / 2;
build(tr, dr, lc, md, t1, t2 * 2);
build(tr, dr, md + 1, rc, t1, t2 * 2 + 1);
seg[t1][t2] = func(seg[t1][t2 * 2], seg[t1][t2 * 2 + 1]);
return;
}
int md = (tr + dr) / 2;
build(tr, md, lc, rc, t1 * 2, t2);
build(md + 1, dr, lc, rc, t1 * 2 + 1, t2);
for(int i = 0; i < (int)seg[t1].size(); i++)
{
seg[t1][i] = func(seg[t1 * 2][i], seg[t1 * 2 + 1][i]);
}
}
void initialization(vector<vector<int>> _a, int _init, F _func)
{
init = _init;
func = _func;
a = _a;
n = (int)a.size();
m = (int)a[0].size();
// cout << func(1, 1e9) << '\n';
seg.assign(n * 8, vector<int>(m * 8, init));
build(0, n - 1, 0, m - 1, 1, 1);
}
void update(int x, int y, int val, int tr, int dr, int lc, int rc, int t1, int t2)
{
if(tr == dr)
{
if(lc == rc)
{
to = t2;
seg[t1][t2] = val;
return;
}
int md = (lc + rc) / 2;
if(y <= md)
update(x, y, val, tr, dr, lc, md, t1, t2 * 2);
else
update(x, y, val, tr, dr, md + 1, rc, t1, t2 * 2 + 1);
seg[t1][t2] = func(seg[t1][t2 * 2], seg[t1][t2 * 2 + 1]);
return;
}
int md = (tr + dr) / 2;
if(x <= md)
update(x, y, val, tr, md, lc, rc, t1 * 2, t2);
else
update(x, y, val, md + 1, dr, lc, rc, t1 * 2 + 1, t2);
for(int i = to; i > 0; i /= 2)
seg[t1][i] = func(seg[t1 * 2][i], seg[t1 * 2 + 1][i]);
}
void update(int x, int y, int val)
{
update(x, y, val, 0, n - 1, 0, m - 1, 1, 1);
}
int query(int r1, int r2, int c1, int c2, int tr, int dr, int lc, int rc, int t1, int t2)
{
if(r2 < tr or dr < r1)
return init;
if(r1 <= tr and dr <= r2)
{
if(c2 < lc or rc < c1)
return init;
if(c1 <= lc and rc <= c2)
return seg[t1][t2];
int md = (lc + rc) / 2;
return func(
query(r1, r2, c1, c2, tr, dr, lc, md, t1, t2 * 2),
query(r1, r2, c1, c2, tr, dr, md + 1, rc, t1, t2 * 2 + 1)
);
}
int md = (tr + dr) / 2;
return func(
query(r1, r2, c1, c2, tr, md, lc, rc, t1 * 2, t2),
query(r1, r2, c1, c2, md + 1, dr, lc, rc, t1 * 2 + 1, t2)
);
}
int query(int r1, int r2, int c1, int c2)
{
return query(r1, r2, c1, c2, 0, n - 1, 0, m - 1, 1, 1);
}
};
SegmentTree2D<function<int (int, int)>> mn, mx;
int n, m;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H, m = W;
a.assign(H, vector<int>(W));
for(int i = 0; i < H * W; i++)
a[R[i]][C[i]] = i;
/* for(int i = 0; i < H; i++)
{
for(int j = 0; j < W; j++)
{
cout << a[i][j] << ' ';
}
cout << '\n';
} */
b.resize(H * W);
for(int i = 0; i < H * W; i++)
b[i] = {R[i], C[i]};
mn.initialization(a, 1e9, [&](int l, int r)
{
return min(l, r);
});
mx.initialization(a, -1e9, [&](int l, int r)
{
return max(l, r);
});
/* for(int i = 0; i < (int)a.size(); i++)
{
for(int j = 0; j < (int)a[0].size(); j++)
{
cout << "( " << mn.query(i, i, j, j) << ' ' << mx.query(i, i, j, j) << " ), ";
}
cout << '\n';
} */
}
int swap_seats(int l, int r) {
int x1 = b[l].first, y1 = b[l].second;
int x2 = b[r].first, y2 = b[r].second;
mn.update(x1, y1, r);
mn.update(x2, y2, l);
mx.update(x1, y1, r);
mx.update(x2, y2, l);
swap(a[x1][y1], a[x2][y2]);
b[l] = {x2, y2};
b[r] = {x1, y1};
/* for(int i = 0; i < (int)a.size(); i++)
{
for(int j = 0; j < (int)a[0].size(); j++)
{
cout << "( " << mn.query(i, i, j, j) << ' ' << mx.query(i, i, j, j) << " ), ";
}
cout << '\n';
} */
x1 = y1 = 1e9;
x2 = y2 = -1e9;
int res = 0;
vector<bool> used(n * m, false);
for(int i = 0; i < (int)b.size(); i++)
{
x1 = min(x1, b[i].first);
y1 = min(y1, b[i].second);
x2 = max(x2, b[i].first);
y2 = max(y2, b[i].second);
if(used[(x2 - x1 + 1) * (y2 - y1 + 1) - 1])
{
continue;
}
used[(x2 - x1 + 1) * (y2 - y1 + 1) - 1] = true;
int mini = 0;
int maxi = (x2 - x1 + 1) * (y2 - y1 + 1) - 1;
if(mx.query(x1, x2, y1, y2) == maxi)
{
res++;
}
}
return res;
}
