#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
struct node{
int s,e,m;
int minv,maxv;
node *l, *r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
int query_min(int i,int j){
if (s==i && e==j) return minv;
else if (j<=m) return l->query_min(i,j);
else if (m<i) return r->query_min(i,j);
else return min(l->query_min(i,m),r->query_min(m+1,j));
}
int query_max(int i,int j){
if (s==i && e==j) return maxv;
else if (j<=m) return l->query_max(i,j);
else if (m<i) return r->query_max(i,j);
else return max(l->query_max(i,m),r->query_max(m+1,j));
}
void update(int i,int j){
if (s==e) minv=maxv=j;
else{
if (i<=m) l->update(i,j);
else r->update(i,j);
minv=min(l->minv,r->minv);
maxv=max(l->maxv,r->maxv);
}
}
};
int h,w;
ii pos[1000005];
int grid[1005][1005];
node* hor[1005];
node* ver[1005];
void print(){
for (int x=0;x<h;x++){
for (int y=0;y<w;y++) printf("%d ",grid[x][y]);
printf("\n");
}
printf("\n");
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int x=0;x<1005;x++) hor[x]=new node(0,1005),ver[x]=new node(0,1005);
h=H,w=W;
for (int x=0;x<h*w;x++){
grid[R[x]][C[x]]=x;
pos[x]=ii(R[x],C[x]);
ver[pos[x].first]->update(pos[x].second,x);
hor[pos[x].second]->update(pos[x].first,x);
}
//print();
}
int swap_seats(int a, int b) {
swap(grid[pos[a].first][pos[a].second],grid[pos[b].first][pos[b].second]);
swap(pos[a],pos[b]);
ver[pos[a].first]->update(pos[a].second,a);
hor[pos[a].second]->update(pos[a].first,a);
ver[pos[b].first]->update(pos[b].second,b);
hor[pos[b].second]->update(pos[b].first,b);
//print();
int x1,x2,y1,y2;
x1=x2=pos[0].first;
y1=y2=pos[0].second;
int s=1;
int biggest=0;
int res=1;
while (s<h*w){
int best=1000000000,tmp;
int dir=-1;
if (0<x1){
tmp=ver[x1-1]->query_min(y1,y2);
if (tmp<best){
best=tmp;
dir=0;
}
}
if (x2<h-1){
tmp=ver[x2+1]->query_min(y1,y2);
if (tmp<best){
best=tmp;
dir=1;
}
}
if (0<y1){
tmp=hor[y1-1]->query_min(x1,x2);
if (tmp<best){
best=tmp;
dir=2;
}
}
if (y2<w-1){
tmp=hor[y2+1]->query_min(x1,x2);
if (tmp<best){
best=tmp;
dir=3;
}
}
if (dir==0){
x1--;
s+=y2-y1+1;
biggest=max(biggest,ver[x1]->query_max(y1,y2));
}
else if (dir==1){
x2++;
s+=y2-y1+1;
biggest=max(biggest,ver[x2]->query_max(y1,y2));
}
else if (dir==2){
y1--;
s+=x2-x1+1;
biggest=max(biggest,hor[y1]->query_max(x1,x2));
}
else{
y2++;
s+=x2-x1+1;
biggest=max(biggest,hor[y2]->query_max(x1,x2));
}
if (biggest==s-1) res++;
//printf("DEBUG: %d %d\n",biggest,s);
//printf("DEBUG: %d %d %d %d\n",x1,x2,y1,y2);
}
return res;
}
