#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
constexpr static int MXN = 1e6;
constexpr static int INF = 1e6;
constexpr static int MXST = MXN<<1;
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
struct SegTree
{
int def;
function<int(int, int)> merge;
int n;
int v[MXST];
void build(int n, vector<int>& a, function<int(int, int)> merge, int def)
{
this->n = n;
this->merge = merge;
this->def = def;
for (int i = n; i < 2*n; i++) v[i] = a[i-n];
for (int i = n-1; i > 0; i--) v[i] = merge(v[i<<1], v[(i<<1)|1]);
}
void set(int i, int val) { for (v[i+=n]=val;i>1;i>>=1) v[i>>1] = merge(v[i], v[i^1]); }
int get(int l, int r)
{
int res = def;
l = max(l, 0);
r = min(r, n);
for (l+=n,r+=n;r>l;r>>=1,l>>=1)
{
if (l&1) res = merge(res, v[l++]);
if (r&1) res = merge(res, v[--r]);
}
return res;
}
};
vector<int> r, c;
SegTree mnr, mxr, mnc, mxc;
int h, w, n;
int counter;
set<int> rects;
int mn(int a, int b) {return min(a,b);}
int mx(int a, int b) {return max(a,b);}
bool is_rect(int i)
{
int rect_size = (mxr.get(0, i+1) - mnr.get(0, i+1) + 1) * (mxc.get(0, i+1) - mnc.get(0, i+1) + 1);
return rect_size == i+1;
}
void create_table()
{
counter = 0;
mnr.build(n, r, mn, INF);
mxr.build(n, r, mx, -INF);
mnc.build(n, c, mn, INF);
mxc.build(n, c, mx, -INF);
for (int i = 0; i < n; i++)
if (is_rect(i))
rects.insert(i);
debug(rects);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
r = R, c = C;
h = H, w = W;
n = h*w;
set<int> rects;
create_table();
}
int swap_seats(int a, int b)
{
if (a > b)
swap(a, b);
for (int i= 0; i < 2; i++)
{
mnr.set(a, r[b]);
mxr.set(a, r[b]);
mnc.set(a, c[b]);
mxc.set(a, c[b]);
swap(a, b);
}
swap(r[a], r[b]);
swap(c[a], c[b]);
for (int i = a; i <= b; i++)
{
bool res = is_rect(i);
if (!res)
rects.erase(i);
if (res)
rects.insert(i);
}
return rects.size();
}
