#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> r, c;
vector<vector<int> > seats;
int cnt[2097152], mn[2097152], lz[2097152];
int L, R, val;
void push(int id, int l, int r){
mn[id] += lz[id];
if(l != r){
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
void update(int id, int l, int r){
push(id, l, r);
if(l > R || r < L) return;
if(l >= L && r <= R){
lz[id] += val;
push(id, l, r);
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m);
update(id << 1 | 1, m + 1, r);
if(mn[id << 1] < mn[id << 1 | 1]){
mn[id] = mn[id << 1];
cnt[id] = cnt[id << 1];
} else if(mn[id << 1] > mn[id << 1 | 1]){
mn[id] = mn[id << 1 | 1];
cnt[id] = cnt[id << 1 | 1];
} else {
mn[id] = mn[id << 1];
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
}
void build(int id, int l, int r){
if(l == r){
cnt[id] = 1;
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
int get(int id, int a, int b, int c, int d){
vector<int> t = {a, b, c, d};
sort(t.begin(), t.end());
return t[id - 1];
}
int n;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H * W;
for(int i = 0; i <= H + 1; i++){
seats.push_back(vector<int>(W + 2, n + 1));
}
r.push_back(0);
c.push_back(0);
build(1, 1, n);
for(int i = 0; i < n; i++){
seats[R[i] + 1][C[i] + 1] = i + 1;
c.push_back(C[i] + 1);
r.push_back(R[i] + 1);
}
val = 1;
for(int i = 0; i <= H; i++){
for(int j = 0; j <= W; j++){
L = get(1, seats[i][j], seats[i + 1][j], seats[i][j + 1], seats[i + 1][j + 1]);
::R = get(2, seats[i][j], seats[i + 1][j], seats[i][j + 1], seats[i + 1][j + 1]) - 1;
if(L <= ::R)update(1, 1, n);
L = get(3, seats[i][j], seats[i + 1][j], seats[i][j + 1], seats[i + 1][j + 1]);
::R = get(4, seats[i][j], seats[i + 1][j], seats[i][j + 1], seats[i + 1][j + 1]) - 1;
if(L <= ::R)update(1, 1, n);
}
}
}
int dx[] = {1, -1, 1, -1};
int dy[] = {1, 1, -1, -1};
int swap_seats(int a, int b){
a++; b++;
val = -1;
int t[] = {a, b};
for(int j = 0; j < 2; j++){
int x = r[t[j]], y = c[t[j]];
for(int i = 0; i < 4; i++){
L = get(1, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]);
R = get(2, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]) - 1;
if(L <= R) update(1, 1, n);
L = get(3, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]);
R = get(4, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]) - 1;
if(L <= R) update(1, 1, n);
}
}
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(seats[r[a]][c[a]], seats[r[b]][c[b]]);
val = 1;
for(int j = 0; j < 2; j++){
int x = r[t[j]], y = c[t[j]];
for(int i = 0; i < 4; i++){
L = get(1, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]);
R = get(2, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]) - 1;
if(L <= R) update(1, 1, n);
L = get(3, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]);
R = get(4, seats[x][y], seats[x + dx[i]][y], seats[x][y + dy[i]], seats[x + dx[i]][y + dy[i]]) - 1;
if(L <= R) update(1, 1, n);
}
}
return cnt[1];
}
