#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct coords {
int a, b, c, d;
coords(){}
coords(int aa, int bb, int cc, int dd) : a(aa), b(bb), c(cc), d(dd) {}
coords(coords &x, coords &y){
a = min(x.a, y.a);
b = max(x.b, y.b);
c = min(x.c, y.c);
d = max(x.d, y.d);
}
};
int n;
int h, w;
vector<coords> st;
void update(int i, coords d){
i += n;
st[i] = d;
for(i /= 2; i > 0; i /= 2){
st[i] = coords(st[i*2], st[i*2+1]);
}
}
coords query(int l, int r){
l += n; r += n;
coords ans = st[l];
while(l <= r){
if(l%2){
ans = coords(ans, st[l++]);
}
if(r%2==0){
ans = coords(ans, st[r--]);
}
l /= 2;
r /= 2;
}
return ans;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
h = H, w = W;
st.resize(2*n);
for(int i = 0; i < n; i++){
update(i, coords(R[i], R[i], C[i], C[i]));
}
}
int swap_seats(int x, int y) {
coords xc = query(x, x), yc = query(y, y);
update(y, xc); update(x, yc);
int i = 0;
int ans = 0;
for(; i < n;){
coords cc = query(0, i);
if((cc.b-cc.a+1)*(cc.d-cc.c+1) == i+1){
ans++;
i++;
} else {
i = (cc.b-cc.a+1)*(cc.d-cc.c+1)-1;
}
}
return ans;
}
