#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int MAXW = 1e3 + 10;
struct node{
int minx, maxx, miny, maxy;
node(int _minx = MAXN, int _maxx = -1, int _miny = MAXN, int _maxy = -1){
minx = _minx;
maxx = _maxx;
miny = _miny;
maxy = _maxy;
}
node operator + (node a){
node ret;
ret.minx = min(minx, a.minx);
ret.maxx = max(maxx, a.maxx);
ret.miny = min(miny, a.miny);
ret.maxy = max(maxy, a.maxy);
return ret;
}
void print(){
printf("%d %d %d %d\n", minx, maxx, miny, maxy);
}
};
vector<int> r, c;
int h, w;
vector<node> seg;
void update(int pos, int ini, int fim, int id, node val);
node query(int pos, int ini, int fim, int p, int q);
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R, c = C;
h = H, w = W;
seg = vector<node> (4 * h * w);
for(int i = 0; i < r.size(); i++)
update(1, 0, h * w - 1, i, node(r[i], r[i], c[i], c[i]));
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
update(1, 0, h * w - 1, a, node(r[a], r[a], c[a], c[a]));
update(1, 0, h * w - 1, b, node(r[b], r[b], c[b], c[b]));
int cur = 0;
int maxi = 0;
int maxr = r[0], minr = r[0], maxc = c[0], minc = c[0];
int ret = 0;
while(cur < h * w){
node val = query(1, 0, h * w - 1, 0, cur);
minr = val.minx;
maxr = val.maxx;
minc = val.miny;
maxc = val.maxy;
if(cur == (maxr - minr + 1) * (maxc - minc + 1) - 1) ret++, cur++;
else cur = (maxr - minr + 1) * (maxc - minc + 1) - 1;
}
return ret;
}
void update(int pos, int ini, int fim, int id, node val){
if(ini > id || fim < id) return;
if(ini == fim){
seg[pos] = val;
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
update(e, ini, mid, id, val);
update(d, mid + 1, fim, id, val);
seg[pos] = seg[e] + seg[d];
}
node query(int pos, int ini, int fim, int p, int q){
if(ini > q || fim < p) return node();
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
return query(e, ini, mid, p, q) + query(d, mid + 1, fim, p, q);
}
