#include "seats.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
struct node{
int a,b,c,d;
} val[4000100];
int l[4000100], r[4000100];
node join(node a, node b){
node c;
c.a = min(a.a,b.a);
c.b = max(a.b,b.b);
c.c = min(a.c,b.c);
c.d = max(a.d,b.d);
return c;
}
void build(int i, int rl, int rr) {
l[i] = rl, r[i] = rr;
if(rl!=rr)
build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, rr);
}
void upd(int i, int pos, int x, int y) {
if(l[i]==r[i])
return(void) (val[i].a=val[i].b=x,val[i].c=val[i].d=y);
if(pos>r[i*2])
upd(i*2+1,pos,x,y);
else upd(i*2,pos,x,y);
val[i]=join(val[i*2],val[i*2+1]);
}
node query(int i, int x, int y) {
if(x<=l[i]&&r[i]<=y)
return val[i];
if(x>r[i]||l[i]>y)
return (node){1000000,0,1000000,0};
return join(query(i*2,x,y),query(i*2+1,x,y));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
build(1,1,H*W);
for(int i = 0; i < r[1]; i++) {
upd(1,i+1,R[i],C[i]);
}
}
int swap_seats(int a, int b) {
a++,b++;
node x = query(1,a,a), y = query(1,b,b);
upd(1,b,x.a,x.c);
upd(1,a,y.a,y.c);
int ans = 0;
for(int i = 1; i <= r[1]; i++) {
x=query(1,1,i);
int sz = (x.b-x.a+1)*(x.d-x.c+1);
if(sz==i) ans++;
else i = max(i,sz-1);
}
return ans;
}
