#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
struct Tree {
vector<int> mins, maxs;
int B;
Tree(){}
Tree(vector<int> R) {
B = 1;
while (B < (int)R.size()) {
B *= 2;
}
maxs.resize(2*B), mins.resize(2*B);
for (int i = B; i < B + (int)R.size(); i++) mins[i] = R[i-B], maxs[i] = R[i-B];
for (int i = B-1; i >= 1; i--) maxs[i] = max(maxs[2*i], maxs[2*i+1]), mins[i] = min(mins[2*i], mins[2*i+1]);
}
pair<int,int> query(int a, int b) {
a += B;
b += B;
pair<int,int> ret = {max(maxs[a], maxs[b]), min(maxs[a], maxs[b])};
while (a / 2 != b / 2) {
if (a % 2 == 0) ret.first = max(ret.first, maxs[a+1]), ret.second = min(ret.second, mins[a+1]);
if (b % 2 == 1) ret.first = max(ret.first, maxs[b-1]), ret.second = min(ret.second, mins[b-1]);
a /= 2; b /= 2;
}
return ret;
}
void update(int a) {
a += B;
a /= 2;
while (a > 0) {
maxs[a] = max(maxs[2*a], maxs[2*a+1]);
mins[a] = min(mins[2*a], mins[2*a+1]);
a /= 2;
}
}
};
int H, W;
Tree tree_r, tree_c;
int B;
void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
H = _H;
W = _W;
tree_r = Tree(R);
tree_c = Tree(C);
B = tree_r.B;
}
int swap_seats(int a, int b) {
swap(tree_r.maxs[a+B], tree_r.maxs[b+B]);
swap(tree_r.mins[a+B], tree_r.mins[b+B]);
swap(tree_c.maxs[a+B], tree_c.maxs[b+B]);
swap(tree_c.mins[a+B], tree_c.mins[b+B]);
tree_r.update(a); tree_r.update(b);
tree_c.update(a); tree_c.update(b);
//puts("swapped");
int ret = 0;
for (int i = 0; i < H*W; i++) {
int rmax, rmin, cmax, cmin;
tie(rmax, rmin) = tree_r.query(0,i);
tie(cmax, cmin) = tree_c.query(0,i);
/*printf("i: %d\n", i);
printf("rmax: %d\n", rmax);
printf("rmin: %d\n", rmin);
printf("cmax: %d\n", cmax);
printf("cmin: %d\n", cmin);*/
int area = (rmax-rmin+1)*(cmax-cmin+1);
ret += (area == i+1);
if (area > i+1) i = area-2;
}
return ret;
}
