#include "seats.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
std::vector<int> r;
struct segment_tree{
vector<pair<pair<int,int>,pair<int,int>>> vec;
pair<pair<int,int>,pair<int,int>> e = {{1e8,-1}, {1e8,-1}};
pair<pair<int,int>,pair<int,int>> merge(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b){
return {{min(a.fi.fi,b.fi.fi), max(a.fi.se,b.fi.se)},{min(a.se.fi,b.se.fi), max(a.se.se,b.se.se)}};
}
void update(int pos, int l, int r, int q, pair<int,int> v){
if(r < q)return;
if(l > q)return;
if(l==r){
vec[pos] = {{v.fi,v.fi},{v.se,v.se}};
return;
}
int m = (l+r)/2;
update(pos*2+1,l,m,q,v);
update(pos*2+2,m+1,r,q,v);
vec[pos] = merge(vec[pos*2+1],vec[pos*2+2]);
}
pair<pair<int,int>,pair<int,int>> query(int pos, int l, int r, int ql, int qr){
if(r < ql)return e;
if(l > qr)return e;
if(ql <= l && r <= qr)return vec[pos];
int m = (l+r)/2;
return merge(query(pos*2+1,l,m,ql,qr),query(pos*2+2,m+1,r,ql,qr));
}
};
segment_tree segtree;
vector<int> R,C;
int H,W;
int N;
set<int> valid;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
::R=R;
::C=C;
::H=H;
::W=W;
::N=H*W;
segtree.vec.resize(4*N+100, segtree.e);
for(int i=0;i<(N);i++){
segtree.update(0,0,N,i,{R[i],C[i]});
auto res = segtree.query(0,0,N,0,i);
// cerr<<i<<": "<<res.fi.fi<<" "<<res.fi.se<<" "<<res.se.fi<<" "<<res.se.se<<"\n";
if(((res.fi.se-res.fi.fi+1)*(res.se.se-res.se.fi+1)) == (i+1)){
valid.insert(i);
}
}
}
int swap_seats(int a, int b) {
// while(valid.lower_bound(a) != valid.upper_bound(b))valid.erase(valid.lower_bound(a));
swap(R[a],R[b]);
swap(C[a],C[b]);
// for(int i=a;i<=b;i++){
// segtree.update(0,0,N,i,{R[i],C[i]});
// auto res = segtree.query(0,0,N,0,i);
// if(((res.fi.se-res.fi.fi+1)*(res.se.se-res.se.fi+1)) == (i+1)){
// valid.insert(i);
// }
// }
valid.clear();
for(int i=0;i<(N);i++){
segtree.update(0,0,N,i,{R[i],C[i]});
auto res = segtree.query(0,0,N,0,i);
// cerr<<i<<": "<<res.fi.fi<<" "<<res.fi.se<<" "<<res.se.fi<<" "<<res.se.se<<"\n";
if(((res.fi.se-res.fi.fi+1)*(res.se.se-res.se.fi+1)) == (i+1)){
valid.insert(i);
}
}
return valid.size();
}
