#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int maxn = 1e3+10;
int n, m;
struct SegmentTree2d
{
int tree[4*maxn][4*maxn];
void upd_y(int nodex, int lx, int rx, int nodey, int ly, int ry, int posy, int v)
{
if (ly == ry)
{
if (lx == rx) tree[nodex][nodey] = v;
else tree[nodex][nodey] = max(tree[2*nodex][nodey], tree[2*nodex+1][nodey]);
return;
}
int mid = (ly+ry)/2;
if (posy <= mid) upd_y(nodex, lx, rx, 2*nodey, ly, mid, posy, v);
else upd_y(nodex, lx, rx, 2*nodey+1, mid+1, ry, posy, v);
tree[nodex][nodey] = max(tree[nodex][2*nodey], tree[nodex][2*nodey+1]);
}
void upd_x(int nodex, int lx, int rx, int posx, int posy, int v)
{
if (lx == rx)
{
upd_y(nodex, lx, rx, 1, 0, m-1, posy, v);
return;
}
int mid = (lx+rx)/2;
if (posx <= mid) upd_x(2*nodex, lx, mid, posx, posy, v);
else upd_x(2*nodex+1, mid+1, rx, posx, posy, v);
upd_y(nodex, lx, rx, 1, 0, m-1, posy, v);
}
int query_y(int nodex, int nodey, int l, int r, int a, int b)
{
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[nodex][nodey];
int mid = (l+r)/2;
return max(query_y(nodex, 2*nodey, l, mid, a, b), query_y(nodex, 2*nodey+1, mid+1, r, a, b));
}
int query_x(int nodex, int l, int r, int ax, int bx, int ay, int by)
{
if (l > bx || r < ax) return 0;
if (l >= ax && r <= bx) return query_y(nodex, 1, 0, m-1, ay, by);
int mid = (l+r)/2;
return max(query_x(2*nodex, l, mid, ax, bx, ay, by), query_x(2*nodex+1, mid+1, r, ax, bx, ay, by));
}
} seg;
vector<int> x, y;
int tab[maxn][maxn];
int pref[maxn][maxn], suf[maxn][maxn];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H, m = W;
for (int i = 0; i < n*m; i++)
{
x.push_back(R[i]);
y.push_back(C[i]);
tab[R[i]][C[i]] = i;
seg.upd_x(1, 0, n-1, R[i], C[i], i);
}
}
int sub_1(void)
{
int mn_x = x[0], mx_x = x[0];
int mn_y = y[0], mx_y = y[0];
int ans = 1;
for (int i = 1; i < n*m; i++)
{
mn_x = min(mn_x, x[i]); mx_x = max(mx_x, x[i]);
mn_y = min(mn_y, y[i]); mx_y = max(mx_y, y[i]);
if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1) ans++;
}
return ans;
}
int sub_2(void)
{
pref[0][0] = tab[0][0];
for (int i = 1; i < m; i++)
pref[0][i] = min(pref[0][i-1], tab[0][i]);
for (int i = 1; i < n; i++)
{
pref[i][0] = min(pref[i-1][0], tab[i][0]);
for (int j = 1; j < m; j++)
pref[i][j] = min({pref[i-1][j], pref[i][j-1], tab[i][j]});
}
suf[n-1][m-1] = tab[n-1][m-1];
for (int i = m-2; i >= 0; i--)
suf[n-1][i] = min(suf[n-1][i+1], tab[n-1][i]);
for (int i = n-2; i >= 0; i--)
{
suf[i][m-1] = min(suf[i+1][m-1], tab[i][m-1]);
for (int j = m-2; j >= 0; j--)
suf[i][j] = min({suf[i+1][j], suf[i][j+1], tab[i][j]});
}
int mn_x = x[0], mx_x = x[0];
int mn_y = y[0], mx_y = y[0];
int ans = 0;
while (true)
{
if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == seg.query_x(1, 0, n-1, mn_x, mx_x, mn_y, mx_y)+1) ans++;
if (mn_x == 0 && mx_x == n-1 && mn_y == 0 && mx_y == m-1) break;
int prox = n*m;
if (mn_x > 0) prox = min(prox, pref[mn_x-1][m-1]);
if (mn_y > 0) prox = min(prox, pref[n-1][mn_y-1]);
if (mx_x < n-1) prox = min(prox, suf[mx_x+1][0]);
if (mx_y < m-1) prox = min(prox, suf[0][mx_y+1]);
mn_x = min(mn_x, x[prox]); mx_x = max(mx_x, x[prox]);
mn_y = min(mn_y, y[prox]); mx_y = max(mx_y, y[prox]);
}
return ans;
}
int swap_seats(int a, int b)
{
int xa = x[a], ya = y[a];
int xb = x[b], yb = y[b];
swap(tab[xa][ya], tab[xb][yb]);
seg.upd_x(1, 0, n-1, xa, ya, tab[xa][ya]);
seg.upd_x(1, 0, n-1, xb, yb, tab[xb][yb]);
x[a] = xb, y[a] = yb;
x[b] = xa, y[b] = ya;
return sub_2();
}
