#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
using namespace std;
vector<int> row, col;
int val[1000][1000], hmax[1000][1000][10], wmax[1000][1000][10];
int h, w;
void calcwmax(int indx) {
for (int i = 0; i < h-1; i++)
wmax[indx][i][0] = val[i+1][indx];
for (int j = 1; j < 10; j++) {
for (int i = 0; i < h; i++) {
if (i + (1<<j) >= h) continue;
wmax[indx][i][j] = max(wmax[indx][i][j-1], wmax[indx][i+(1<<(j-1))][j-1]);
}
}
}
void calchmax(int indx) {
for (int i = 0; i < w-1; i++)
hmax[indx][i][0] = val[indx][i+1];
for (int j = 1; j < 10; j++) {
for (int i = 0; i < w; i++) {
if (i + (1<<j) >= w) continue;
hmax[indx][i][j] = max(hmax[indx][i][j-1], hmax[indx][i+(1<<(j-1))][j-1]);
}
}
}
int findwmax(int indx, int l, int r) {
int ans = val[l][indx];
for (int i = 9; i >= 0; i--) {
if (l + (1 << i) > r) continue;
ans = max(ans, wmax[indx][l][i]);
l = l + (1 << i);
}
return ans;
}
int findhmax(int indx, int l, int r) {
int ans = val[indx][l];
for (int i = 9; i >= 0; i--) {
if (l + (1 << i) > r) continue;
ans = max(ans, hmax[indx][l][i]);
l = l + (1 << i);
}
return ans;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
row = R;
col = C;
h = H;
w = W;
for (int i = 0; i < h*w; i++)
val[R[i]][C[i]] = i;
for (int i = 0; i < h; i++)
calchmax(i);
for (int j = 0; j < w; j++)
calcwmax(j);
}
int swap_seats(int A, int B) {
swap(row[A], row[B]);
swap(col[A], col[B]);
val[row[A]][col[A]] = A;
val[row[B]][col[B]] = B;
calchmax(row[A]);
calchmax(row[B]);
calcwmax(col[A]);
calcwmax(col[B]);
int t = row[0], b = row[0], l = col[0], r = col[0], mx = 0, ans = 1;
while (t > 0 || b < h-1 || l > 0 || r < w-1) {
int now = h*w+5;
if (t != 0)
now = min(now, findhmax(t-1, l, r));
if (b != h-1)
now = min(now, findhmax(b+1, l, r));
if (l != 0)
now = min(now, findwmax(l-1, t, b));
if (r != w-1)
now = min(now, findwmax(r+1, t, b));
if (t != 0 && findhmax(t-1, l, r) == now)
t--;
else if (b != h-1 && findhmax(b+1, l, r) == now)
b++;
else if (l != 0 && findwmax(l-1, t, b) == now)
l--;
else if (r != w-1 && findwmax(r+1, t, b) == now)
r++;
// cout << l << ' ' << t << ' ' << r << ' ' << b << '\n';
// cout << now << ' ' << mx << '\n';
mx = max(mx, now);
if ((r-l+1)*(b-t+1) == mx+1) ans++;
}
// cout << "=======\n";
return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
