#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){
//cout<<"B "<<l<<" "<<r<<" "<<mina.F<<" "<<mina.S<<endl;
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();
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
cerr<<"STARTED"<<endl;
n = H, m = W;
FOR(i, n*m){
update({R[i], C[i]}, i);
}
cerr<<"DONE"<<endl;
}
int swap_seats(int a, int b) {
pair<ii, ii> temp1 = query(a, a);
pair<ii, ii> temp2 = query(b, b);
//cout<<temp1.F.F<<" "<<temp1.F.S<<" "<<temp1.S.F<<" "<<temp1.S.S<<endl;
update(temp1.F, b);
update(temp2.F, a);
int r=0;
int i=0;
int cnt=0;
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);
cnt++;
if(q==i+1) r++, i++;
else i = q-1;
}
//cerr<<cnt<<endl;
return r;
}
