#include "seats.h"
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 1000010
int N, H, W;
vector<int> R, C;
int a[3*MAXN];
int seg[MAXN*6], lazy[MAXN*6], num[MAXN*6];
int t[4];
void mkseg(int idx, int l, int r){
num[idx]=r-l+1;
if(l<r){
int m=l+r>>1;
mkseg(idx*2, l, m);
mkseg(idx*2+1, m+1, r);
}
}
void updseg(int idx, int l, int r, int x, int y, int z){
//if(idx==1) printf("(%d %d %d)\n", x, y, z);
if(x<=l&&r<=y){
lazy[idx]+=z;
seg[idx]+=z;
}
else if(l<=y&&x<=r){
int m=l+r>>1;
lazy[idx*2]+=lazy[idx];
lazy[idx*2+1]+=lazy[idx];
seg[idx*2]+=lazy[idx];
seg[idx*2+1]+=lazy[idx];
lazy[idx]=0;
updseg(idx*2, l, m, x, y, z);
updseg(idx*2+1, m+1, r, x, y, z);
if(seg[idx*2]<seg[idx*2+1]){
seg[idx]=seg[idx*2];
num[idx]=num[idx*2];
}
else if(seg[idx*2+1]<seg[idx*2]){
seg[idx]=seg[idx*2+1];
num[idx]=num[idx*2+1];
}
else{
seg[idx]=seg[idx*2];
num[idx]=num[idx*2]+num[idx*2+1];
}
}
}
void updcor(int i, int j, int z){
t[0]=a[i*(W+2)+j];
t[1]=a[i*(W+2)+j+1];
t[2]=a[(i+1)*(W+2)+j];
t[3]=a[(i+1)*(W+2)+j+1];
sort(t, t+4);
if(t[0]<t[1]) updseg(1, 0, N-1, t[0], t[1]-1, z);
if(t[2]<t[3]) updseg(1, 0, N-1, t[2], t[3]-1, z);
}
void updsea(int i, int j, int z){
//printf("{%d %d %d}\n", i, j, z);
updcor(i, j, z);
updcor(i, j+1, z);
updcor(i+1, j, z);
updcor(i+1, j+1, z);
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
H=h;
W=w;
N=H*W;
R=r;
C=c;
for(int i=0; i<N; i++) a[(R[i]+1)*(W+2)+C[i]+1]=i;
for(int i=0; i<=H+1; i++) a[i*(W+2)]=a[i*(W+2)+W+1]=N;
for(int i=0; i<=W+1; i++) a[i]=a[(H+1)*(W+2)+i]=N;
mkseg(1, 0, N-1);
for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) updcor(i, j, 1);
//printf("[%d]\n", num[1]);
}
int swap_seats(int x, int y) {
updsea(R[x], C[x], -1);
updsea(R[y], C[y], -1);
swap(a[(R[x]+1)*(W+2)+C[x]+1], a[(R[y]+1)*(W+2)+C[y]+1]);
swap(R[x], R[y]);
swap(C[x], C[y]);
updsea(R[x], C[x], 1);
updsea(R[y], C[y], 1);
return num[1];
}
