#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 1000006;
int n, m;
int x[N], y[N];
struct ban
{
int minx, maxx;
int miny, maxy;
ban()
{
minx = miny = N;
maxx = maxy = -1;
}
ban(int x, int y)
{
minx = maxx = x;
miny = maxy = y;
}
};
ban mer(const ban& l, const ban& r)
{
ban res;
res.minx = min(l.minx, r.minx);
res.maxx = max(l.maxx, r.maxx);
res.miny = min(l.miny, r.miny);
res.maxy = max(l.maxy, r.maxy);
return res;
}
ban t[N * 4];
void ubd(int tl, int tr, int x, pair<int, int> y, int pos)
{
if (tl == tr)
{
t[pos] = ban(y.fi, y.se);
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
ban qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return ban();
if (tl == l && tr == r)
{
return t[pos];
}
int m = (tl + tr) / 2;
return mer(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
n = H;
m = W;
for (int i = 0; i < n * m; ++i)
{
x[i] = R[i];
y[i] = C[i];
}
for (int i = 0; i < n * m; ++i)
ubd(0, n * m - 1, i, m_p(x[i], y[i]), 1);
}
int swap_seats(int a, int b)
{
swap(x[a], x[b]);
swap(y[a], y[b]);
ubd(0, n * m - 1, a, m_p(x[a], y[a]), 1);
ubd(0, n * m - 1, b, m_p(x[b], y[b]), 1);
int ans = 0;
for (int i = 0; i < n * m; ++i)
{
ban u = qry(0, n * m - 1, 0, i, 1);
if ((u.maxx - u.minx + 1) * (u.maxy - u.miny + 1) == i + 1)
++ans;
}
return ans;
}
