#include <bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int maxn = 1100;
pair<int,int>cords[maxn*maxn];
int h, w;
struct node {
public:
pair<int,int>minv, maxv;
} tree[4*maxn*maxn];
node mergef(node a, node b) {
node c;
c.minv.first = min(a.minv.first, b.minv.first);
c.minv.second = min(a.minv.second, b.minv.second);
c.maxv.first = max(a.maxv.first, b.maxv.first);
c.maxv.second = max(a.maxv.second, b.maxv.second);
return c;
}
void update(int x, pair<int,int> uval, int li=0, int ri=h*w-1, int index=1) {
if(li == ri) {
tree[index].minv.first = tree[index].maxv.first = uval.first;
tree[index].minv.second = tree[index].maxv.second = uval.second;
}
else {
int mid = (li+ri)/2;
if(x<=mid) update(x, uval, li, mid, 2*index);
else update(x, uval, mid+1, ri, 2*index+1);
tree[index] = mergef(tree[2*index], tree[2*index+1]);
}
}
node query(int ql, int qr, int li=0, int ri=h*w-1, int index=1) {
if(li > qr || ri < ql) return {{INT_MAX, INT_MAX}, {INT_MIN, INT_MIN}};
else if(li >= ql && ri <= qr) return tree[index];
else {
int mid = (li+ri)/2;
return mergef(query(ql,qr,li,mid,2*index), query(ql,qr,mid+1,ri,2*index+1));
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H; w = W;
for(int i=0;i<H*W;i++) {
cords[i].first = R[i];
cords[i].second = C[i];
update(i, cords[i]);
}
}
int swap_seats(int a, int b) {
swap(cords[a], cords[b]);
update(a, cords[a]);
update(b, cords[b]);
int nxi = 0;
int br = 0;
for(int i=0;i<h*w;i = nxi) {
node x = query(0, i);
int min_x = x.minv.first;
int min_y = x.minv.second;
int max_x = x.maxv.first;
int max_y = x.maxv.second;
if(i + 1 == (max_x-min_x+1)*(max_y-min_y+1)) {
nxi = i + 1;
br++;
}
else {
nxi = max(i + 1, (max_x-min_x+1)*(max_y-min_y+1) - 1);
}
}
return br;
}
