#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
std::vector<int> r;
std :: vector <int> c;
const int NMAX = 1e6 + 1;
int cnt = 0;
int n, m;
int t[4 * NMAX][4];
void update(int v, int l, int r, int pos, pii val){
if(l > pos || r < pos) return;
if(l == r){
t[v][0] = t[v][2] = val.f;
t[v][1] = t[v][3] = val.s;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v + 1, m + 1, r, pos, val);
t[v][0] = max(t[2 * v][0], t[2 * v + 1][0]);
t[v][1] = max(t[2 * v][1], t[2 * v + 1][1]);
t[v][2] = min(t[2 * v][2], t[2 *v + 1][2]);
t[v][3] = min(t[2 * v][3], t[2 * v + 1][3]);
}
int get(int v, int l, int r, int st, int fin, int ind){
if(l > fin || r < st){
if(ind < 2) return 0;
return 1e9;
}
if(l >= st && r <= fin) return t[v][ind];
int m = (l + r) / 2;
int x = get(2 * v, l, m, st, fin, ind);
int y = get(2 * v + 1, m + 1, r, st, fin, ind);
if(ind < 2) return max(x, y);
return min(x, y);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
n = H, m = W;
for(int i = 0; i < n * m; i++){
// cout << r[i] << ' ' << c[i] << "\n";
update(1, 1, n * m, i + 1, {r[i], c[i]});
}
}
int swap_seats(int a, int b) {
if(a > b) swap(a, b);
//cout << cnt;
update(1, 1, n * m, a + 1, {r[b], c[b]});
update(1, 1, n * m, b + 1, {r[a], c[a]});
swap(r[b], r[a]);
swap(c[b], c[a]);
int cnt = 0;
for(int i = 0; i < n * m; i++){
int x = get(1, 1, n * m, 1, i + 1, 0);
int y = get(1, 1, n * m, 1, i + 1, 1);
int z = get(1, 1, n * m, 1, i + 1, 2);
int v = get(1, 1, n * m, 1, i + 1, 3);
int xx = x - z + 1;
int yy = y - v + 1;
if(xx * yy == i + 1) cnt++;
if(i == n * m - 1) break;
x = max(x, r[i + 1]);
y = max(y, c[i + 1]);
z = min(z, r[i + 1]);
v = min(v, c[i + 1]);
i = (x - z + 1) * (y - v + 1) - 2;
}
return cnt;
}
