#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
#define FL (p<<1)|1
#define FR (p<<1)+2
#define row 0
#define col 1
int h ,w ,n;
vector <pair<int ,int>> pos;
int tree[2][1003][4*1003];
void update(bool roc ,int mn ,int idx ,int val ,int l=0 ,int r=1000 ,int p=0){
if(l == r){
tree[roc][mn][p] = val;
return;
}
int mid = (l+r)>>1;
if(idx <= mid) update(roc ,mn ,idx ,val ,l ,mid ,FL);
else update(roc ,mn ,idx ,val ,mid+1 ,r ,FR);
tree[roc][mn][p] = max(tree[roc][mn][FL] ,tree[roc][mn][FR]);
}
int ask(bool roc ,int mn ,int ql ,int qr ,int l=0 ,int r=1000 ,int p=0){
if(ql <= l && r <= qr)
return tree[roc][mn][p];
if(r < ql || qr < l)
return -1e9;
int mid = (l+r)>>1;
return max(ask(roc ,mn ,ql ,qr ,l ,mid ,FL),
ask(roc ,mn ,ql ,qr ,mid+1 ,r ,FR));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H ,w = W ,n = H*W;
assert(H <= 1000 && W <= 1000);
for(int i=0; i<n; i++){
update(row ,R[i] ,C[i] ,i);
update(col ,C[i] ,R[i] ,i);
pos.push_back({R[i] ,C[i]});
}
}
int swap_seats(int a, int b) {
int ret = 1;
update(row ,pos[a].first ,pos[a].second ,b);
update(col ,pos[a].second ,pos[a].first ,b);
update(row ,pos[b].first ,pos[b].second ,a);
update(col ,pos[b].second ,pos[b].first ,a);
swap(pos[a] ,pos[b]);
int curr_max_seat = 0;
int min_r = pos[0].first ,min_c = pos[0].second;
int max_r = pos[0].first ,max_c = pos[0].second;
for(int i=1; i<n; ){ ///O(H+W = 2000)
int lst_min_r = min_r ,lst_min_c = min_c;
int lst_max_r = max_r ,lst_max_c = max_c;
min_r = min(min_r ,pos[i].first);
min_c = min(min_c ,pos[i].second);
max_r = max(max_r ,pos[i].first);
max_c = max(max_c ,pos[i].second);
while(lst_max_c < max_c)
curr_max_seat = max(curr_max_seat ,ask(col ,++lst_max_c ,lst_min_r ,lst_max_r));
while(min_c < lst_min_c)
curr_max_seat = max(curr_max_seat ,ask(col ,--lst_min_c ,lst_min_r ,lst_max_r));
while(lst_max_r < max_r)
curr_max_seat = max(curr_max_seat ,ask(row ,++lst_max_r ,lst_min_c ,lst_max_c));
while(min_r < lst_min_r)
curr_max_seat = max(curr_max_seat ,ask(row ,--lst_min_r ,lst_min_c ,lst_max_c));
//cout << i << " - (" << min_c << ',' << min_r << ") : (" << max_c << ',' << max_r << ") = " << curr_max_seat << endl;
if(curr_max_seat == i)
ret++ ,i++;
else
i = curr_max_seat;
}
return ret;
}
