#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e6+5;
int r[maxn], c[maxn];
int n, m;
struct node
{
int mnr, mxr;
int mnc, mxc;
node(){}
node(int a, int b, int c, int d) : mnr(a), mxr(b), mnc(c), mxc(d) {}
bool operator == (node other) const
{
if(mnr != other.mnr) return false;
if(mnc != other.mnc) return false;
if(mxr != other.mxr) return false;
if(mxc != other.mxc) return false;
return true;
}
};
bool in(node x, node y)
{
return y.mnr<= x.mnr && y.mnc<= x.mnc && x.mxr<= y.mxr && x.mxc<= y.mxc;
}
node st[4*maxn];
node pull(node &x, node &y)
{
return node(min(x.mnr, y.mnr), max(x.mxr, y.mxr), min(x.mnc, y.mnc), max(x.mxc, y.mxc));
}
void update(int x, int dr, int dc, int p = 1, int L = 0, int R = n*m-1)
{
if(L == R)
{
st[p] = node(dr, dr, dc, dc);
return;
}
int M = (L+R)/2;
if(x<= M) update(x, dr, dc, 2*p, L, M);
else update(x, dr, dc, 2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
node ask(int i, int j, int p = 1, int L = 0, int R = n*m-1)
{
if(i> R || j< L) return node(1e9, 0, 1e9, 0);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
node x = ask(i, j, 2*p, L, M);
node y = ask(i, j, 2*p+1, M+1, R);
return pull(x, y);
}
int border(node &x, int p = 1, int L = 0, int R = n*m-1)
{
if(L == R)
{
if(in(st[p], x)) return L;
return L-1;
}
node here = st[2*p];
int M = (L+R)/2;
if(in(st[p], x)) return border(x, 2*p+1, M+1, R);
return border(x, 2*p, L, M);
}
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++)
{
r[i] = R[i]; c[i] = C[i];
update(i, r[i], c[i]);
}
}
int swap_seats(int a, int b)
{
update(a, r[b], c[b]);
update(b, r[a], c[a]);
swap(r[a], r[b]);
swap(c[a], c[b]);
int st = 0;
int ans = 0;
int cnt = 0;
while(st< n*m)
{
node x = ask(0, st);
int lo = border(x);
int sz = (x.mxr-x.mnr+1)*(x.mxc-x.mnc+1);
ans += st+1<= sz && sz<= lo+1;
st = lo+1;
cnt++;
}
// printf("incremented %d times\n", cnt);
return ans;
}
