#warning H=1
#include<bits/stdc++.h>
#include "seats.h"
#define fi first
#define se second
using namespace std;
const int N=1e6;
const int PP=11e5;
const int INF=1e9+7;
struct Mn
{
int w,cnt;
Mn(int _w=0,int _cnt=0) : w(_w), cnt(_cnt) {};
void operator+=(const Mn &oth)
{
if(oth.w<w && oth.cnt>0)
{
w=oth.w;
cnt=oth.cnt;
}
else if(oth.w==w)
cnt+=oth.cnt;
return;
}
Mn operator+(const Mn &oth)
{
Mn tmp=*this;
tmp+=oth;
return tmp;
}
bool operator<(const Mn &oth) const
{
return w<oth.w;
}
};
struct Tree
{
Mn ans,ansc0,ansd0;
int c,d;
set<int> sty;
};
int n,hi,wi;
pair<int,int> tab[N+10];
int pot;
Tree tree[2*PP+10];
tuple<Mn,Mn,Mn> dfs(int i,int l,int r,int c,int d)
{
//cerr<<i<<" "<<l<<" "<<r<<" "<<c<<" "<<d<<"\n";
if(l==r)
{
//cerr<<"xd1\n";
Mn w=max(tree[i].ans,Mn(d-c+1-min(n,r),(r<=n)));
Mn c0=max(tree[i].ansc0,Mn(d+1-min(n,r),(r<=n)));
Mn d0=max(tree[i].ansd0,Mn(-c+1-min(n,r),(r<=n)));
return {w,c0,d0};
}
if(tree[2*i+1].d<=d)
{
//cerr<<"xd2\n";
auto [w,c0,d0]=dfs(i,l,r,c,-1);
c0={d+1-min(n,r),1};
w={d0.w+d,d0.cnt};
return {w,c0,d0};
}
if(tree[2*i+1].c>=c)
{
//cerr<<"xd3\n";
auto [w,c0,d0]=dfs(i,l,r,wi+1,d);
d0={-c+1-min(n,r),1};
w={c0.w-c,c0.cnt};
return {w,c0,d0};
}
bool brc,brd;
brc=(tree[2*i].c>=c);
brd=(tree[2*i].d<=d);
int mid=(l+r)/2;
if(brc && brd)
{
//cerr<<"xd4\n";
auto [w,c0,d0]=dfs(2*i+1,mid+1,r,c,d);
w+=Mn(d-c+1-min(n,r),1);
c0+=Mn(d+1-min(n,r),1);
d0+=Mn(-c+1-min(n,r),1);
return {w,c0,d0};
}
if(brc)
{
//cerr<<"xd5\n";
auto [w,c0,d0]=dfs(2*i+1,mid+1,r,c,-1);
auto [w1,c01,d01]=dfs(2*i,l,mid,c,d);
w+=w1;
c0+=c01;
d0+=d01;
return {w,c0,d0};
}
if(brd)
{
//cerr<<"xd6\n";
auto [w,c0,d0]=dfs(2*i+1,mid+1,r,wi+1,d);
auto [w1,c01,d01]=dfs(2*i,l,mid,c,d);
w+=w1;
c0+=c01;
d0+=d01;
return {w,c0,d0};
}
//cerr<<"xd7\n";
auto [w,c0,d0]=dfs(2*i,l,mid,c,d);
w+=tree[2*i+1].ans;
c0+=tree[2*i+1].ansc0;
d0+=tree[2*i+1].ansd0;
return {w,c0,d0};
}
void solve(int i,int l,int r)
{
//cerr<<"solve "<<i<<" "<<l<<" "<<r<<"\n";
if(l==r)
{
tree[i].c=wi;
tree[i].d=0;
tree[i].ans=Mn(-INF,0);
tree[i].ansc0=Mn(-INF,0);
tree[i].ansd0=Mn(-INF,0);
if(!tree[i].sty.empty())
{
int c=*tree[i].sty.begin(),d=*prev(tree[i].sty.end());
tree[i].c=min(tree[i].c,c);
tree[i].d=max(tree[i].d,d);
tree[i].ans=Mn(tree[i].d-tree[i].c+1-min(n,r),(r<=n));
tree[i].ansc0=Mn(tree[i].d+1-min(n,r),(r<=n));
tree[i].ansd0=Mn(-tree[i].c+1-min(n,r),(r<=n));
}
return;
}
tree[i].c=min(tree[2*i].c,tree[2*i+1].c);
tree[i].d=max(tree[2*i].d,tree[2*i+1].d);
tree[i].ans=tree[2*i].ans+tree[2*i+1].ans;
tree[i].ansc0=tree[2*i].ansc0+tree[2*i+1].ansc0;
tree[i].ansd0=tree[2*i].ansd0+tree[2*i+1].ansd0;
if(tree[i].sty.empty())
return;
int c=*tree[i].sty.begin(),d=*prev(tree[i].sty.end());
tree[i].c=min(tree[i].c,c);
tree[i].d=max(tree[i].d,d);
auto [t0,t1,t2]=dfs(i,l,r,c,d);
tree[i].ans=t0;
tree[i].ansc0=t1;
tree[i].ansd0=t2;
return;
}
void del_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
if(rs<l || r<ls)
return;
if(ls<=l && r<=rs)
{
tree[i].sty.erase(c.se);
solve(i,l,r);
return;
}
int mid=(l+r)/2;
del_t(2*i,l,mid,ls,rs,c);
del_t(2*i+1,mid+1,r,ls,rs,c);
solve(i,l,r);
return;
}
void add_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
if(rs<l || r<ls)
return;
if(ls<=l && r<=rs)
{
tree[i].sty.insert(c.se);
solve(i,l,r);
return;
}
int mid=(l+r)/2;
add_t(2*i,l,mid,ls,rs,c);
add_t(2*i+1,mid+1,r,ls,rs,c);
solve(i,l,r);
return;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
n=H*W;
hi=H;
wi=W;
for(int i=1;i<=n;i++)
tab[i]={R[i-1],C[i-1]};
for(pot=1;pot<n;pot*=2);
for(int i=2*pot-1;i>=1;i--)
{
tree[i].c=wi;
tree[i].d=0;
tree[i].ans=Mn(-INF,0);
tree[i].ansc0=Mn(-INF,0);
tree[i].ansd0=Mn(-INF,0);
}
#warning buid tree faster
for(int i=1;i<=n;i++)
add_t(1,1,pot,i,n,tab[i]);
//for(int i=1;i<2*pot;i++)
// cerr<<"tree["<<i<<"].ans=("<<tree[i].ans.w<<","<<tree[i].ans.cnt<<") c="<<tree[i].c<<" d="<<tree[i].d<<"\n";
return;
}
int swap_seats(int a,int b)
{
a++;
b++;
del_t(1,1,pot,a,n,tab[a]);
del_t(1,1,pot,b,n,tab[b]);
swap(tab[a],tab[b]);
add_t(1,1,pot,a,n,tab[a]);
add_t(1,1,pot,b,n,tab[b]);
//for(int i=1;i<2*pot;i++)
// cerr<<"tree["<<i<<"].ans=("<<tree[i].ans.w<<","<<tree[i].ans.cnt<<") c="<<tree[i].c<<" d="<<tree[i].d<<"\n";
return tree[1].ans.cnt;
}
