#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000100
#define MID ((l+r)/2)
#define ll long long
#define F first
#define S second
typedef pair<int, int> ii;
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
int n, m;
static int rl, rr;
static ii val;
static int x;
static pair<ii, ii> RAND = {{MOD, MOD}, {0,0}};
struct seg_tree{
seg_tree *left=0;
seg_tree *right=0;
pair<ii, ii> v = RAND;
void update(int l=0, int r=MOD){
if(l==r && l==x){
v = {val, val};
}
else if(l>x || r<x) assert(0);
else{
pair<ii, ii> ans1 = RAND;
pair<ii, ii> ans2 = RAND;
if(x<=MID){
if(!left) left = new seg_tree;
left->update(l, MID);
}
else{
if(!right) right = new seg_tree;
right->update(MID+1, r);
}
if(left) ans1 = left->v;
if(right) ans2 = right->v;
v = {{min(ans1.F.F, ans2.F.F), min(ans1.F.S, ans2.F.S)}, {max(ans1.S.F, ans2.S.F), max(ans1.S.S, ans2.S.S)}};
}
}
pair<ii,ii> query(int l=0, int r=MOD){
if(rl<=l && r<=rr) return v;
else if(r<rl || rr<l) return RAND;
else{
if(!left) left = new seg_tree;
if(!right) right = new seg_tree;
pair<ii, ii> ans1 = left->query(l, MID);
pair<ii, ii> ans2 = right->query(MID+1, r);
return {{min(ans1.F.F, ans2.F.F), min(ans1.F.S, ans2.F.S)}, {max(ans1.S.F, ans2.S.F), max(ans1.S.S, ans2.S.S)}};
}
}
};
seg_tree seg;
pair<ii, ii> query(int l, int r){
rl = l;
rr = r;
return seg.query();
}
void update(ii v, int xx){
val = v;
x = xx;
seg.update();
}
vector<ii> pos;
int maxx[1020000];
int minx[1020000];
int maxy[1020000];
int miny[1020000];
int pr[1020000];
int tot=0;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
cerr<<"STARTED"<<endl;
n = H, m = W;
pos.resize(n*m);
FOR(i, n*m){
pos[i] = {R[i], C[i]};
update({R[i], C[i]}, i);
}
int i=1;
minx[0] = MOD;
miny[0] = MOD;
while(i<=n*m){
//cerr<<i<<" ";
maxx[i] = max(maxx[i-1], pos[i-1].F);
minx[i] = min(minx[i-1], pos[i-1].F);
maxy[i] = max(maxy[i-1], pos[i-1].S);
miny[i] = min(miny[i-1], pos[i-1].S);
int q = (maxx[i]-minx[i] + 1) * (maxy[i] - miny[i] + 1);
if(q==i) tot++, pr[i] = 1;
else pr[i] = 0;
i++;
}
cerr<<"DONE"<<endl;
}
int swap_seats(int a, int b) {
/*
if(n+m<=2000){
int r=0;
int i=0;
pair<ii, ii> temp1 = query(a, a);
pair<ii, ii> temp2 = query(b, b);
update(temp1.F, b);
update(temp2.F, a);
while(i<n*m){
//cerr<<i<<" ";
pair<ii, ii> ans = query(0, i);
int q = (ans.S.F - ans.F.F+1) * (ans.S.S - ans.F.S+1);
if(q==i+1) r++, i++;
else i = q-1;
}
}
//else{*/
if(a>b) swap(a,b);
swap(pos[a], pos[b]);
int i = a+1;
while(i<=b+1){
//cerr<<i<<" ";
maxx[i] = max(maxx[i-1], pos[i-1].F);
minx[i] = min(minx[i-1], pos[i-1].F);
maxy[i] = max(maxy[i-1], pos[i-1].S);
miny[i] = min(miny[i-1], pos[i-1].S);
int q = (maxx[i]-minx[i] + 1) * (maxy[i] - miny[i] + 1);
if(q==i){
if(!pr[i]) tot++, pr[i] = 1;
}
else{
if(pr[i]) tot--, pr[i] = 0;
}
i++;
}
//cerr<<endl;
return tot;
//}
//return r;
}
