#include "seats.h"
#include <set>
#include <iostream>
using namespace std;
int n, m;
vector<int> x;
vector<int> y;
vector<set<int>> xx;
vector<set<int>> yy;
struct segtree {
int zeroSum = -1e9;
int oper(int a, int b) {
return max(a, b);
}
vector<int> sums;
int size;
void set(int i, int x, int n, int L, int R) {
if (R == L + 1) {
sums[n] = x;
return;
}
int M = (L + R) >> 1;
if (i < M) {
set(i, x, 2 * n + 1, L, M);
} else {
set(i, x, 2 * n + 2, M, R);
}
sums[n] = oper(sums[2 * n + 1], sums[2 * n + 2]);
}
int getmax(int l, int r, int n, int L, int R) {
if (l >= R || L >= r) return zeroSum;
if (L >= l && R <= r) {
return sums[n];
}
int M = (L + R) >> 1;
return oper(getmax(l, r, 2 * n + 1, L, M), getmax(l, r, 2 * n + 2, M, R));
}
void init(int n) {
size = 1;
while (size < n) size *= 2;
sums.assign(2 * size, zeroSum);
}
void init(vector<int> a) {
int n = a.size();
init(n);
size = 1;
while (size < n) size *= 2;
sums.assign(2 * size, zeroSum);
for (int i = 0; i < n; i++) {
sums[size - 1 + i] = a[i];
}
for (int i = size - 2; i >= 0; i--) {
sums[i] = oper(sums[2 * i + 1], sums[2 * i + 2]);
}
}
void set(int i, int x) {
set(i, x, 0, 0, size);
}
int getmax(int l, int r) {
return getmax(l, r, 0, 0, size);
}
};
segtree minx, maxx, miny, maxy;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
x = R;
y = C;
n = H;
m = W;
maxx.init(x);
for (auto &i : x) i = -i;
minx.init(x);
for (auto &i : x) i = -i;
maxy.init(y);
for (auto &i : y) i = -i;
miny.init(y);
for (auto &i : y) i = -i;
xx.resize(n);
yy.resize(m);
for (int i = 0; i < n * m; i++) {
xx[x[i]].insert(i);
yy[y[i]].insert(i);
}
}
int swap_seats(int a, int b) {
xx[x[a]].erase(a);
xx[x[b]].erase(b);
yy[y[a]].erase(a);
yy[y[b]].erase(b);
swap(x[a], x[b]);
swap(y[a], y[b]);
xx[x[a]].insert(a);
xx[x[b]].insert(b);
yy[y[a]].insert(a);
yy[y[b]].insert(b);
maxx.set(a, x[a]);
minx.set(a, -x[a]);
maxy.set(a, y[a]);
miny.set(a, -y[a]);
maxx.set(b, x[b]);
minx.set(b, -x[b]);
maxy.set(b, y[b]);
miny.set(b, -y[b]);
set<int> cand;
for (int i = 0; i < n; i++) {
if (xx[i].empty()) continue;
int k = *xx[i].begin();
if (k != 0) cand.insert(k);
}
for (int i = 0; i < m; i++) {
if (yy[i].empty()) continue;
int k = *yy[i].begin();
if (k != 0) cand.insert(k);
}
int res = 1;
for (int k : cand) {
int s = (maxx.getmax(0, k) + minx.getmax(0, k) + 1) *
(maxy.getmax(0, k) + miny.getmax(0, k) + 1);
// cout << "! " << k << " " << s << "\n";
if (s == k) {
res++;
}
}
return res;
}
