#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif
struct segtree {
int nt = 1;
vector<int> mn, cnt, add;
void init(int N, vector<int> &a, vector<int> &p) {
while (nt < N) {
nt <<= 1;
}
mn = vector<int>(2*nt, 1 << 30);
cnt = vector<int>(2*nt, 1);
add = vector<int>(2*nt);
mn[nt] = 2;
for (int i = 1; i < N; i++) {
mn[nt+i] = mn[nt+i-1];
if (a[p[i]-1] < i) {
mn[nt+i]--;
} else {
mn[nt+i]++;
}
if (a[p[i]+1] < i) {
mn[nt+i]--;
} else {
mn[nt+i]++;
}
}
for (int i = nt-1; i >= 1; i--) {
merge(i, i*2, i*2|1);
}
}
void prop(int k) {
mn[k] += add[k];
if (k < nt) {
add[k*2] += add[k];
add[k*2|1] += add[k];
}
add[k] = 0;
}
void update(int l, int r, int k, int tl, int tr, int val) {
prop(k);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
add[k] += val;
prop(k);
return;
}
int c = (tl + tr) / 2;
update(l, r, k*2, tl, c, val);
update(l, r, k*2|1, c+1, tr, val);
merge(k, k*2, k*2|1);
}
void merge(int i, int c1, int c2) {
if (mn[c1] == mn[c2]) {
cnt[i] = cnt[c1] + cnt[c2];
} else if (mn[c1] < mn[c2]) {
cnt[i] = cnt[c1];
} else {
cnt[i] = cnt[c2];
}
mn[i] = min(mn[c1], mn[c2]);
}
};
vector<vector<int>> m;
vector<int> a, pos;
int N;
segtree st;
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
N = W_; // H = 1
a = vector<int>(N+2, N);
for (int i = 0; i < N; i++) {
a[C_[i]+1] = i;
}
pos = C_;
for (auto &e : pos) {
e++;
}
st.init(N, a, pos);
}
int swap_seats(int u, int v) {
// TODO: Handle case where u and v are adjacent
st.update(min(a[pos[u]-1], u), max(a[pos[u]-1], u)-1, 1, 0, st.nt-1, -1);
st.update(min(a[pos[u]+1], u), max(a[pos[u]+1], u)-1, 1, 0, st.nt-1, -1);
st.update(min(a[pos[v]-1], v), max(a[pos[v]-1], v)-1, 1, 0, st.nt-1, -1);
st.update(min(a[pos[v]+1], v), max(a[pos[v]+1], v)-1, 1, 0, st.nt-1, -1);
swap(a[pos[u]], a[pos[v]]);
swap(pos[u], pos[v]);
st.update(min(a[pos[u]-1], u), max(a[pos[u]-1], u)-1, 1, 0, st.nt-1, 1);
st.update(min(a[pos[u]+1], u), max(a[pos[u]+1], u)-1, 1, 0, st.nt-1, 1);
st.update(min(a[pos[v]-1], v), max(a[pos[v]-1], v)-1, 1, 0, st.nt-1, 1);
st.update(min(a[pos[v]+1], v), max(a[pos[v]+1], v)-1, 1, 0, st.nt-1, 1);
return st.cnt[1];
}
