#include "seats.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
const int INF=0x3f3f3f3f;
struct Segtree1{ //1D
int N;
vector<int>dat;
Segtree1(){}
Segtree1(int n){
N=1;while(N<n)N<<=1;
dat=vector<int>(2*N);
}
void update(int k,int x){
k+=N;dat[k]=x;
while(k>1){
k>>=1;
dat[k]=max(dat[k*2],dat[k*2+1]);
}
}
int query(int l,int r){
int res=0;
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1)res=max(res,dat[l++]);
if(r&1)res=max(res,dat[--r]);
}
return res;
}
};
struct Segtree2{ //2D
int H,W;
vector<Segtree1>dat;
Segtree2(){}
Segtree2(int h,int w){
H=1;while(H<h)H<<=1;
W=1;while(W<w)W<<=1;
dat=vector<Segtree1>(2*H,Segtree1(W));
}
void update(int x,int y,int val){
x+=H;dat[x].update(y,val);
while(x>1){
x>>=1;
dat[x].update(y,max(dat[x*2].dat[y+W],dat[x*2+1].dat[y+W]));
}
}
int query(int l1,int r1,int l2,int r2){
int res=0;
for(l1+=H,r1+=H;l1<r1;l1>>=1,r1>>=1){
if(l1&1)res=max(res,dat[l1++].query(l2,r2));
if(r1&1)res=max(res,dat[--r1].query(l2,r2));
}
return res;
}
};
struct Segtree{
int N;
vector<int>dat;
function<int(int,int)>f;
int ini;
Segtree(){}
Segtree(int n,int ini,function<int(int,int)>f):ini(ini),f(f){
N=1;while(N<n)N<<=1;
dat=vector<int>(2*N,ini);
}
void update(int k,int x){
k+=N;dat[k]=x;
while(k>1){
k>>=1;
dat[k]=f(dat[k*2],dat[k*2+1]);
}
}
int query(int l,int r){
int res=ini;
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1)res=f(res,dat[l++]);
if(r&1)res=f(res,dat[--r]);
}
return res;
}
};
static int h,w;
static vector<int>r,c;
Segtree2 range;
Segtree rmin,rmax,cmin,cmax;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
rmin=cmin=Segtree(H*W,INF,[](int a,int b){return min(a,b);});
rmax=cmax=Segtree(H*W,0,[](int a,int b){return max(a,b);});
range=Segtree2(H,W);
h=H;w=W;
r=R;c=C;
rep(i,h*w){
rmin.update(i,r[i]);
rmax.update(i,r[i]);
cmin.update(i,c[i]);
cmax.update(i,c[i]);
range.update(r[i],c[i],i);
}
}
int swap_seats(int a, int b) {
if(a>b)swap(a,b);
swap(r[a],r[b]);
swap(c[a],c[b]);
rmin.update(a,r[a]);
rmin.update(b,r[b]);
rmax.update(a,r[a]);
rmax.update(b,r[b]);
cmin.update(a,c[a]);
cmin.update(b,c[b]);
cmax.update(a,c[a]);
cmax.update(b,c[b]);
range.update(r[a],c[a],a);
range.update(r[b],c[b],b);
int ans=0;
int cur=0;
while(cur<h*w){
int l1=rmin.query(0,cur+1),r1=rmax.query(0,cur+1)+1;
int l2=cmin.query(0,cur+1),r2=cmax.query(0,cur+1)+1;
int val=range.query(l1,r1,l2,r2);
assert(val>=cur);
if(val==cur){
ans++;
cur++;
continue;
}
cur=val;
}
return ans;
}
