#include "seats.h"
#include <bits/stdc++.h>
#define size(x) (int)((x).size())
using namespace std;
const int p2 = 1<<20;
struct SumSegtree {
SumSegtree() {
t = new int [p2*2];
lz = new int [p2*2];
cnt = new int [p2*2];
for (int i = 0; i < p2*2; i++) {
t[i] = 0;
lz[i] = 0;
cnt[i] = 1;
}
for (int i = p2-1; i >= 1; i--) {
cnt[i] = cnt[i*2] + cnt[i*2+1];
}
}
void push(int x, int span) {
if (x < p2) {
lz[x*2] += lz[x];
lz[x*2+1] += lz[x];
}
t[x] += lz[x];
// assert(t[x] >= 2);
lz[x] = 0;
}
void pull(int x) {
t[x] = min(t[x*2], t[x*2+1]);
cnt[x] = 0;
if (t[x] == t[x*2]) {
cnt[x] += cnt[x*2];
}
if (t[x] == t[x*2+1]) {
cnt[x] += cnt[x*2+1];
}
}
void upd(int rb, int re, int rv, int qn = 1, int qb = 0, int qe = p2-1) {
if (rb > qe || qb > re) push(qn, qe-qb+1);
else if (rb <= qb && qe <= re) {
lz[qn] += rv;
push(qn, qe-qb+1);
}
else {
push(qn, qe-qb+1);
int qm = (qb+qe)/2;
upd(rb, re, rv, qn*2, qb, qm);
upd(rb, re, rv, qn*2+1, qm+1, qe);
pull(qn);
}
}
int get(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
push(qn, qe-qb+1);
if (rb > qe || qb > re) return 0;
else if (rb <= qb && qe <= re) {
// return t[qn];
return (t[qn] == 2 ? cnt[qn] : 0);
}
else {
int qm = (qb+qe)/2;
int r = get(rb, re, qn*2, qb, qm)+get(rb, re, qn*2+1, qm+1, qe);
pull(qn);
return r;
}
}
int* t, * lz, * cnt;
};
SumSegtree st;
int n;
vector<int> b, posOf;
void give_initial_chart(int H, int W, std::vector<int> row, std::vector<int> col) {
st = SumSegtree();
assert(H == 1);
n = W;
assert(size(row) == n && size(col) == n);
posOf = vector<int>(n);
for (int i = 0; i < n; i++) {
assert(row[i] == 0);
posOf[col[i]] = i;
}
b = col;
for (int i = -1; i < n; i++) {
int c = n;
if (0 <= i && i < n) c = b[i];
int d = n;
if (0 <= i+1 && i+1 < n) d = b[i+1];
if (c > d) swap(c, d);
assert(c < d);
st.upd(c, d-1, 1);
// vector<int> curState(n, 0);
// for (int j = 0; j < n; j++) curState[j] = st.get(j, j);
// cout << "Case #" << i << ": ";
// for (int j = 0; j < n; j++) {
// cout << curState[j] << ' ';
// }
// cout << endl;
// cout << endl;
}
}
void doit(int v, int x, int ch) {
int secV = n;
if (0 <= x && x < n) secV = b[x];
if (v > secV) swap(v, secV);
if (v < secV) st.upd(v, secV-1, ch);
}
int swap_seats(int x, int y) {
assert(0 <= x && x < n);
assert(0 <= y && y < n);
if (posOf[x]+1 == posOf[y] || posOf[x]-1 == posOf[y]) {
if (!(posOf[x]+1 == posOf[y])) {
swap(x, y);
}
doit(x, posOf[x]-1, -1);
doit(y, posOf[y]+1, -1);
doit(x, posOf[y]+1, 1);
doit(y, posOf[x]-1, 1);
}
else {doit(x, posOf[x]-1, -1);
doit(x, posOf[x]+1, -1);
doit(y, posOf[y]-1, -1);
doit(y, posOf[y]+1, -1);
doit(y, posOf[x]-1, 1);
doit(y, posOf[x]+1, 1);
doit(x, posOf[y]-1, 1);
doit(x, posOf[y]+1, 1);
}
int res = st.get(0, n-1);
swap(b[posOf[x]], b[posOf[y]]);
swap(posOf[x], posOf[y]);
return res;
}
