#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;
pair<int,int> p[kax];
int mnr[4 * kax],mxr[4 * kax],mxc[4 * kax],mnc[4 * kax];
int at,h,w,l,r;
void buildr(int n,int s,int e){
if(s == e){
mnr[n] = mxr[n] = p[s-1].first;
return;
}
buildr(n*2,s,(s+e)/2);
buildr(n*2+1,(s+e)/2+1,e);
mnr[n] = min(mnr[n*2],mnr[n*2+1]);
mxr[n] = max(mxr[n*2],mxr[n*2+1]);
}
void buildc(int n,int s,int e){
if(s == e){
mnc[n] = mxc[n] = p[s-1].second;
return;
}
buildc(n*2,s,(s+e)/2);
buildc(n*2+1,(s+e)/2+1,e);
mnc[n] = min(mnc[n*2],mnc[n*2+1]);
mxc[n] = max(mxc[n*2],mxc[n*2+1]);
}
void updater(int n,int s,int e){
if(s > at || e < at)
return;
if(s == e){
mnr[n] = mxr[n] = p[s-1].first;
return;
}
updater(n*2,s,(s+e)/2);
updater(n*2+1,(s+e)/2+1,e);
mnr[n] = min(mnr[n*2],mnr[n*2+1]);
mxr[n] = max(mxr[n*2],mxr[n*2+1]);
}
void updatec(int n,int s,int e){
if(s > at || e < at)
return;
if(s == e){
mnc[n] = mxc[n] = p[s-1].second;
return;
}
updatec(n*2,s,(s+e)/2);
updatec(n*2+1,(s+e)/2+1,e);
mnc[n] = min(mnc[n*2],mnc[n*2+1]);
mxc[n] = max(mxc[n*2],mxc[n*2+1]);
}
int getmnr(int n,int s,int e){
if(s > r || e < l)
return 1e9;
if(s >= l && e <= r)
return mnr[n];
return min(getmnr(n*2,s,(s+e)/2) , getmnr(n*2+1,(s+e)/2+1,e));
}
int getmnc(int n,int s,int e){
if(s > r || e < l)
return 1e9;
if(s >= l && e <= r)
return mnc[n];
return min(getmnc(n*2,s,(s+e)/2) , getmnc(n*2+1,(s+e)/2+1,e));
}
int getmxr(int n,int s,int e){
if(s > r || e < l)
return 0;
if(s >= l && e <= r)
return mxr[n];
return max(getmxr(n*2,s,(s+e)/2) , getmxr(n*2+1,(s+e)/2+1,e));
}
int getmxc(int n,int s,int e){
if(s > r || e < l)
return 0;
if(s >= l && e <= r)
return mxc[n];
return max(getmxc(n*2,s,(s+e)/2) , getmxc(n*2+1,(s+e)/2+1,e));
}
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;
buildr(1,1,h*w);
buildc(1,1,h*w);
}
int swap_seats(int a, int b) {
swap(p[a],p[b]);
at = a+1;
updater(1,1,h*w);
updatec(1,1,h*w);
at = b+1;
updater(1,1,h*w);
updatec(1,1,h*w);
int ans = 0,cur = 0;
l = 1;
while(1){
if(cur >= h*w)
break;
r = cur+1;
int u = getmnr(1,1,h*w);
int d = getmxr(1,1,h*w);
int a = getmnc(1,1,h*w);
int b = getmxc(1,1,h*w);
if((d - u + 1) * (b - a + 1) <= cur)
break;
// if(cur == 4){
// printf("\n");
// cout << u << ' ' << d << endl;
// cout << a << ' ' << b << endl;
// return 0;
// }
if((d - u + 1) * (b - a + 1) == cur + 1){
ans++;
cur++;
}else if((d - u + 1) * (b - a + 1) - 1 > cur){
cur = (d - u + 1) * (b - a + 1) - 1;
}
}
return ans;
}
