#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e6+42;
int n,m;
struct info
{
int min_x,min_y,max_x,max_y;
};
info tree[4*nmax];
pair<int,int> where[nmax];
info my_merge(info a,info b)
{
info ret;
ret.min_x=min(a.min_x,b.min_x);
ret.max_x=max(a.max_x,b.max_x);
ret.min_y=min(a.min_y,b.min_y);
ret.max_y=max(a.max_y,b.max_y);
return ret;
}
void update(int node,int l,int r,int pos)
{
if(l==r)
{
tree[node].min_x=where[pos].first;
tree[node].max_x=where[pos].first;
tree[node].min_y=where[pos].second;
tree[node].max_y=where[pos].second;
return;
}
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos);
else update(node*2+1,av+1,r,pos);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
info query(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree[node];
int av=(l+r)/2;
info ret;
ret.min_x=1e9;
ret.max_x=0;
ret.min_y=1e9;
ret.max_y=0;
if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
return ret;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
n=H;
m=W;
for(int i=0;i<H*W;i++)
{
where[i]={R[i],C[i]};
}
for(int i=0;i<H*W;i++)
update(1,0,H*W-1,i);
}
int eval()
{
int ret=0,i=0;
for(int i=0;i<n*m;i++)
{
info cur=query(1,0,n*m-1,i,i);
//cout<<i<<" -> "<<cur.min_x<<" "<<cur.max_x<<" "<<cur.min_y<<" "<<cur.max_y<<endl;
}
while(i<n*m)
{
info cur=query(1,0,n*m-1,0,i);
int area=(cur.max_x-cur.min_x+1)*(cur.max_y-cur.min_y+1);
//cout<<i<<" -> "<<area<<" "<<cur.min_x<<" "<<cur.max_x<<" "<<cur.min_y<<" "<<cur.max_y<<endl;
if(i+1==area)ret++;
i=max(i+1,area-1);
}
return ret;
}
int swap_seats(int a, int b)
{
swap(where[a],where[b]);
update(1,0,n*m-1,a);
update(1,0,n*m-1,b);
return eval();
}
