#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;
node seg[4 * MAXN];
void build(int pos, int ini, int fim);
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, vector<int> R, vector<int> C) {
r = R, c = C;
h = H, w = W;
build(1, 0, h * w - 1);
}
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 ret = 0;
for (int i = 0; i < h*w; ){
node val = query(1, 0, h*w-1, 0, i);
int mn_x = val.minx, mx_x = val.maxx, mn_y = val.miny, mx_y = val.maxy;
if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1) ret++;
i = max(i+1, (mx_x-mn_x+1)*(mx_y-mn_y+1)-1);
}
return ret;
}
void build(int pos, int ini, int fim){
if(ini == fim){
seg[pos] = node(r[ini], r[ini], c[ini], c[ini]);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
build(e, ini, mid);
build(d, mid + 1, fim);
seg[pos] = seg[e] + seg[d];
}
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);
}
