#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define endl "\n"
using namespace std;
struct STmn{
int len=1;
vector<int> tree;
STmn(int l){
while(len<l)
len*=2;
tree=vector<int>(2*len,1e9);
}
void update(int idx,int v){
idx+=len;
tree[idx]=v;
for(idx/=2;idx>=1;idx/=2)
tree[idx]=min(tree[idx*2],tree[idx*2+1]);
}
int query(int l,int r){
int res = 1e9;
l+=len,r+=len;
while(l<=r){
if(l%2==1)
res = min(res,tree[l++]);
if(r%2==0)
res = min(res,tree[r--]);
l/=2,r/=2;
}
return res;
}
};
struct Inter{
int mnv,t,l,r,seg;
};
int N,M;
vector<vector<int>> G;
vector<STmn> segcol;
vector<STmn> seglig;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
N=H,M=W;
G.resize(N);
for(int i=0;i<N;i++){
G[i].resize(M);
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
G[R[i*M+j]][C[i*M+j]]=i*M+j;
}
}
for(int _=0;_<N;_++)
seglig.push_back(STmn(M));
for(int _=0;_<M;_++)
segcol.push_back(STmn(N));
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
seglig[i].update(j,G[i][j]);
}
}
for(int j=0;j<M;j++){
for(int i=0;i<N;i++){
segcol[j].update(i,G[i][j]);
}
}
}
int swap_seats(int a, int b){
int v1 = G[a/M][a%M],v2=G[b/M][b%M];
seglig[a/M].update(a%M,v2);
seglig[b/M].update(b%M,v1);
segcol[a%M].update(a/M,v2);
segcol[b%M].update(b/M,v1);
swap(G[a/M][a%M],G[b/M][b%M]);
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cout << G[i][j] << ' ';
}
cout << endl;
}
int res = 1;
int k=N*M;
int mnrem=N*M;
pair<int,int> c1={0,0},c2={N-1,M-1};
while(k>1){
//cout << c1.first << ' ' << c1.second << ' ';
//cout << c2.first << ' ' << c2.second << endl;
if(mnrem==k){
res++;
}
vector<Inter> inter;
int i1=c1.first,i2=c2.first;
int j1=c1.second,j2=c2.second;
inter.push_back({seglig[i1].query(j1,j2),0,j1,j2,i1});
inter.push_back({segcol[j2].query(i1,i2),1,i1,i2,j2});
inter.push_back({seglig[i2].query(j1,j2),0,j1,j2,i2});
inter.push_back({segcol[j1].query(i1,i2),1,i1,i2,j1});
bool same=false;
int mxv = -1;
int mxidx = -1;
for(int i=0;i<4;i++){
if(inter[i].mnv==inter[(i+1)%4].mnv)
same=true;
if(mxv<inter[i].mnv){
mxv=inter[i].mnv;
mxidx=i;
}
}
assert(mxv!=-1&&mxidx!=-1);
//cout << ": "<<mxidx << ' ' << mxv << endl;
if(same){
if(inter[mxidx].t==0){
int seg1 = inter[mxidx].seg;
int l1=inter[mxidx].l,r1=inter[mxidx].r;
int seg2 = inter[(mxidx+1)%4].seg;
int l2=inter[(mxidx+1)%4].l,r2=inter[(mxidx+1)%4].r;
if(seglig[seg1].query(l1,r1-1)<segcol[seg2].query(l2+1,r2)){
mxidx=(mxidx+1)%4;
}
}
else{
int seg1 = inter[mxidx].seg;
int l1=inter[mxidx].l,r1=inter[mxidx].r;
int seg2 = inter[(mxidx+1)%4].seg;
int l2=inter[(mxidx+1)%4].l,r2=inter[(mxidx+1)%4].r;
if(segcol[seg1].query(l1,r1-1)<seglig[seg2].query(l2+1,r2)){
mxidx=(mxidx+1)%4;
}
}
int seg = inter[mxidx].seg;
int l=inter[mxidx].l,r=inter[mxidx].r;
if(inter[mxidx].t==0)
mnrem=min(mnrem,seglig[seg].query(l,r));
else
mnrem=min(mnrem,segcol[seg].query(l,r));
k-=r-l+1;
if(mxidx==0)
c1.first++;
else if(mxidx==1)
c2.second--;
else if(mxidx==2)
c2.first--;
else
c1.second++;
}
}
return res;
}
