#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
int m,n;
vector<int> x,y;
struct node
{
int mnx,mxx,mny,mxy;
friend node operator+(const node &a,const node &b)
{
node ret;
ret.mnx = min(a.mnx,b.mnx),ret.mxx = max(a.mxx,b.mxx);
ret.mny = min(a.mny,b.mny),ret.mxy = max(a.mxy,b.mxy);
return ret;
}
}tree[N << 1];
void build(int l,int r,int idx)
{
if(l==r) return void(tree[idx] = {x[l],x[l],y[l],y[l]});
int m = (l+r)/2;
build(l,m,idx*2),build(m+1,r,idx*2+1);
tree[idx] = tree[idx*2]+tree[idx*2+1];
}
void update(int l,int r,int idx,int x,int a,int b)
{
if(x>r or x<l) return;
if(l==r) return void(tree[idx] = {a,a,b,b});
int m = (l+r)/2;
update(l,m,idx*2,x,a,b),update(m+1,r,idx*2+1,x,a,b);
tree[idx] = tree[idx*2]+tree[idx*2+1];
}
node read(int l,int r,int idx,int x,int y)
{
if(x>r or y<l) return {INT_MAX,INT_MIN,INT_MAX,INT_MIN};
if(x<=l and y>=r) return tree[idx];
int m = (l+r)/2;
return read(l,m,idx*2,x,y)+read(m+1,r,idx*2+1,x,y);
}
void give_initial_chart(int H, int W,vector<int> R,vector<int> C)
{
m = H,n = W,x = R,y = C;
build(0,m*n-1,1);
}
int swap_seats(int a,int b)
{
int xa = x[a],xb = x[b],ya = y[a],yb = y[b];
update(0,m*n-1,1,a,xb,yb),update(0,m*n-1,1,b,xa,ya);
swap(x[a],x[b]),swap(y[a],y[b]);
int ans = 0,now = 0;
while(now<m*n)
{
node rx = read(0,m*n-1,1,0,now);
int val = (rx.mxx-rx.mnx+1)*(rx.mxy-rx.mny+1)-1;
if(val==now) ans++,now++;
else now = val;
}
return ans;
}
