#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
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;
}
struct node{
node *l, *r;
pair<int, int> mini;
pair<int, int> maxi;
void update(){
mini.first = min(l->mini.first, r->mini.first);
mini.second = min(l->mini.second, r->mini.second);
maxi.first = max(l->maxi.first, r->maxi.first);
maxi.second = max(l->maxi.second, r->maxi.second);
}
};
vector< pair<int, int> > v;
void Build(node* root, int left, int right){
if(left == right){
root->maxi.second = root->mini.second = v[left-1].second;
root->maxi.first = root->mini.first = v[left-1].first;
return;
}
int mid = (left+right)/2;
root->l = new node{NULL,NULL,{0,0},{0,0}};
root->r = new node{NULL,NULL,{0,0},{0,0}};
Build(root->l, left, mid);
Build(root->r, mid+1, right);
root->update();
}
void update(node* root, int left, int right, int index, pair<int, int> p){
if(left > index || right < index) return;
if(left == index && right == index){
root->maxi.second = root->mini.second = p.second;
root->maxi.first = root->mini.first = p.first;
return;
}
int mid = (left+right)/2;
update(root->l, left, mid, index, p);
update(root->r, mid+1, right, index, p);
root->update();
}
tuple<int, int, int, int> query(node* root, int left, int right, int qLeft, int qRight){
if(left > qRight || right < qLeft) return {INT_MAX, INT_MAX, INT_MIN, INT_MIN};
if(left >= qLeft && right <= qRight){
return {root->mini.first, root->mini.second, root->maxi.first, root->maxi.second};
}
int mid = (left+right)/2;
tuple<int, int, int, int> p = query(root->l, left, mid, qLeft, qRight);
tuple<int, int, int, int> q = query(root->r, mid+1, right, qLeft, qRight);
return {min(get<0>(p), get<0>(q)), min(get<1>(p), get<1>(q)), max(get<2>(p), get<2>(q)), max(get<3>(p), get<3>(q))};
}
int h, w;
node* root = new node{NULL,NULL,{0,0},{0,0}};
#undef int
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
#define int long long
h = H;
w = W;
v.resize(h*w);
for(int i = 0; i < H*W; i++){
v[i] = make_pair(R[i], C[i]);
}
Build(root, 1, H*W);
}
#undef int
int swap_seats(int a, int b) {
#define int long long
update(root, 1, h*w, a+1, v[b]);
update(root, 1, h*w, b+1, v[a]);
swap(v[b], v[a]);
int curr = 1;
int ans = 0;
while(curr <= h*w){
tuple<int, int, int, int> q = query(root, 1, h*w, 1, curr);
pair<int, int> maxi = {get<2>(q), get<3>(q)};
pair<int, int> mini = {get<0>(q), get<1>(q)};
//if(curr == 5) break;
if((maxi.first - mini.first + 1)*(maxi.second - mini.second + 1) == curr){
ans++;
curr++;
}else{
assert((maxi.first - mini.first + 1)*(maxi.second - mini.second + 1) > curr);
curr = (maxi.first - mini.first + 1)*(maxi.second - mini.second + 1);
}
//cout << ans << endl;
}
return ans;
#undef int
}
