#include <bits/stdc++.h>
#include "seats.h"
#define F first
#define S second
#define SZ(a) ((int)(a).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
ii mip(ii a, ii b){
return {min(a.F,b.F),min(a.S,b.S)};
}
ii mxp(ii a, ii b){
return {max(a.F,b.F),max(a.S,b.S)};
}
struct mix{
ii mx, mi;
mix(ii p){
mx=p;
mi=p;
}
mix(){ }
mix(ii a, ii b){
mx=a, mi=b;
}
ll area(){
return (mx.F-mi.F+1)*(mx.S-mi.S+1);
}
};
mix comb(mix a, mix b){
mix r;
r.mx=mxp(a.mx, b.mx);
r.mi=mip(a.mi, b.mi);
return r;
}
std::vector<ii> p;
std::vector<mix> heap;
int h, w, np2;
void upd(int i, ii p, int a=0, int b=np2, int h=1){
if(i<a || b<=i)
return;
if(b-a==1){
heap[h]=mix(p);
return;
}
upd(i,p,a,(a+b)/2,h*2);
upd(i,p,(a+b)/2,b,h*2+1);
heap[h]=comb(heap[2*h],heap[2*h+1]);
}
mix que(int i, int j, int a=0, int b=np2, int h=1){
if(j<=a || b<=i)
return mix({0,0},{h,w});
if(i<=a && b<=j)
return heap[h];
return comb(que(i,j,a,(a+b)/2,h*2),que(i,j,(a+b)/2,b,h*2+1));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H; w=W;
np2=1;
while (np2<h*w)
np2<<=1;
p.resize(h*w);
heap.resize(np2*2);
for(int i=0; i<h*w; i++)
heap[i+np2]=p[i]={R[i],C[i]};
for(int i=np2-1; i>0; i--)
heap[i]=comb(heap[i*2],heap[i*2+1]);
}
int swap_seats(int a, int b) {
swap(p[a],p[b]);
upd(a,p[a]);
upd(b,p[b]);
int cc=0;
for(int i=0; i<h*w; i++){
int a=que(0,i+1).area();
if(a==i+1)
cc++;
else
i=a-2;
}
return cc;
}
