#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1010;
const int kax = nax*nax;
struct node{
short u,d,a,b;
}seg[3*kax];
pair<short,short> p[kax];
int at,h,w,l,r,cnt,n;
void build(int n,int s,int e){
if(s == e){
seg[n] = {p[s-1].first,p[s-1].first,p[s-1].second,p[s-1].second};
return;
}
build(n*2,s,(s+e)/2);
build(n*2+1,(s+e)/2+1,e);
seg[n] = {min(seg[n*2].u,seg[n*2+1].u) , max(seg[n*2].d,seg[n*2+1].d) ,
min(seg[n*2].a,seg[n*2+1].a) , max(seg[n*2].b,seg[n*2+1].b) };
}
void update(int n,int s,int e){
if(s == e){
seg[n] = {p[s-1].first,p[s-1].first,p[s-1].second,p[s-1].second};
return;
}
if((s+e)/2 >= at)
update(n*2,s,(s+e)/2);
if((s+e)/2+1 <= at)
update(n*2+1,(s+e)/2+1,e);
seg[n] = {min(seg[n*2].u,seg[n*2+1].u) , max(seg[n*2].d,seg[n*2+1].d) ,
min(seg[n*2].a,seg[n*2+1].a) , max(seg[n*2].b,seg[n*2+1].b) };
}
node get(int n,int s,int e){
if(s >= l && e <= r)
return seg[n];
node x,y,z;
x = y = {(int)1e4,0,(int)1e4,0};
if((s+e)/2 >= l)
x = get(n*2,s,(s+e)/2);
if((s+e)/2+1 <= r)
y = get(n*2+1,(s+e)/2+1,e);
z = {min(x.u,y.u) , max(x.d,y.d) , min(x.a,y.a) , max(x.b,y.b) };
return z;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
for(int i=0;i<H*W;i++)
p[i] = {R[i],C[i]};
h = H;
w = W;
n = h*w;
build(1,1,n);
}
int swap_seats(int a, int b) {
swap(p[a],p[b]);
at = a+1;
update(1,1,n);
at = b+1;
update(1,1,n);
int ans = 0,cur = 0;
l = 1;
while(1){
if(cur >= n)
break;
cnt++;
r = cur+1;
node g = get(1,1,n);
short u = g.u;
short d = g.d;
short a = g.a;
short b = g.b;
int q = (d - u + 1) * (b - a + 1);
if(q == cur + 1){
ans++;
cur++;
}else{
cur = q - 1;
}
}
return ans;
}
