#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
inline int min(int &a, int &b){
if(a < b) return a;
return b;
}
inline int max(int &a, int &b){
if(a < b) return b;
return a;
}
vector< pair<int, int > > mini;
vector< pair<int, int > > maxi;
void update(int root){
mini[root].first = min(mini[2*root].first, mini[2*root+1].first);
mini[root].second = min(mini[2*root].second, mini[2*root+1].second);
maxi[root].first = max(maxi[2*root].first, maxi[2*root+1].first);
maxi[root].second = max(maxi[2*root].second, maxi[2*root+1].second);
}
vector< pair<int, int> > v;
void Build(int right){
for(int root = right*2-1; root >= right; root--){
//cout << "SET " << root << endl;
maxi[root].first = mini[root].first = v[root-right].first;
maxi[root].second = mini[root].second = v[root-right].second;
}
for(int i = right-1; i > 0; i--){
update(i);
}
}
void update(int right, int index, pair<int, int> p){
index += right;
maxi[index].first = mini[index].first = p.first;
maxi[index].second = mini[index].second = p.second;
index /= 2;
while(index){
update(index);
index/=2;
}
}
tuple<int, int, int, int> query(int right, int qLeft, int qRight){
qLeft += right;
qRight += right;
tuple<int, int, int, int> tup = {INT_MAX, INT_MAX, INT_MIN, INT_MIN};
while(qLeft < qRight){
if(qLeft&1){
tup = {min(get<0>(tup), mini[qLeft].first), min(get<1>(tup), mini[qLeft].second), max(get<2>(tup), maxi[qLeft].first), max(get<3>(tup), maxi[qLeft].second)};
qLeft++;
}
if(qRight&1){
qRight--;
tup = {min(get<0>(tup), mini[qRight].first), min(get<1>(tup), mini[qRight].second), max(get<2>(tup), maxi[qRight].first), max(get<3>(tup), maxi[qRight].second)};
}
qLeft >>= 1;
qRight >>= 1;
}
return tup;
}
int h, w;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H;
w = W;
v.resize(h*w);
mini.resize(4*(h*w+1));
maxi.resize(4*(h*w+1));
for(int i = 0; i < H*W; i++){
v[i] = make_pair(R[i], C[i]);
}
Build(H*W);
}
int swap_seats(int a, int b) {
update(h*w, a, v[b]);
update(h*w, b, v[a]);
//cout << "MIAOU" << endl;
swap(v[b], v[a]);
int curr = 1;
int ans = 0;
while(curr <= h*w){
tuple<int, int, int, int> q = query(h*w, 0, curr);
pair<int, int> maxii = {get<2>(q), get<3>(q)};
pair<int, int> minii = {get<0>(q), get<1>(q)};
if((maxii.first - minii.first + 1)*(maxii.second - minii.second + 1) == curr){
ans++;
curr++;
}else{
assert((maxii.first - minii.first + 1)*(maxii.second - minii.second + 1) > curr);
curr = (maxii.first - minii.first + 1)*(maxii.second - minii.second + 1);
}
//cout << ans << endl;
}
return ans;
}
