#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
struct segment_tree {
ll n, nt;
vector<ll> tree, cnt, laz;
void recalc(ll i) {
if (i >= nt) return;
if (tree[2*i] < tree[2*i+1]) {
tree[i] = tree[2*i];
cnt[i] = cnt[2*i];
}
else if (tree[2*i] > tree[2*i+1]) {
tree[i] = tree[2*i+1];
cnt[i] = cnt[2*i+1];
}
else {
tree[i] = tree[2*i];
cnt[i] = cnt[2*i] + cnt[2*i+1];
}
}
void prop(ll i) {
tree[i] += laz[i];
if (i < nt) {
laz[2*i] += laz[i];
laz[2*i+1] += laz[i];
}
laz[i] = 0;
}
segment_tree() { }
segment_tree(ll n, vector<ll> &a) : n(n) {
nt = 1;
while (nt < n) nt *= 2;
tree = vector<ll>(2*nt, 1ll << 62ll);
cnt = vector<ll>(2*nt, 1);
laz = vector<ll>(2*nt);
for (ll i = 0; i < n; i++) tree[nt+i] = a[i];
for (ll i = nt-1; i > 0; i--) recalc(i);
}
ll global_cnt() {
return tree[1] > 2 ? 0 : cnt[1];
}
void range_add(ll k, ll tl, ll tr, ll l, ll r, ll val) {
prop(k);
if (r < tl || l > tr) return;
if (l <= tl && r >= tr) {
laz[k] += val;
prop(k);
return;
}
ll mid = (tl + tr) / 2;
range_add(2*k, tl, mid, l, r, val);
range_add(2*k+1, mid+1, tr, l, r, val);
recalc(k);
}
void range_add(ll l, ll r, ll val) { return range_add(1, 0, nt-1, l, r, val); }
void print(ll k) {
prop(k);
if (k >= nt) {
cerr << tree[k] << ' ';
}
else {
print(2*k);
print(2*k+1);
}
if (k == 1) cerr << endl;
}
};
ll h, w;
vector<ll> pos, val;
segment_tree tree;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H; w = W;
pos = vector<ll>(w);
val = vector<ll>(w+2, 1ll << 62ll);
for (ll i = 0; i < w; i++) {
pos[i] = C[i];
val[pos[i]+1] = i;
}
vector<ll> a(w, 2);
vector<bool> state(w+2);
state[pos[0]+1] = true;
for (ll i = 1; i < w; i++) {
ll p = pos[i]+1;
a[i] = a[i-1];
ll &cur = a[i];
cur -= (state[p-1] != state[p]) + (state[p] != state[p+1]);
state[p] = true;
cur += (state[p-1] != state[p]) + (state[p] != state[p+1]);
}
tree = segment_tree(w, a);
}
pair<ll, ll> range(ll x, ll y) {
return {min(val[x], val[y]), max(val[x], val[y])-1};
}
int swap_seats(int A, int B) {
ll a = A, b = B;
ll pa = pos[a]+1, pb = pos[b]+1;
{
auto al = range(pa-1, pa);
auto ar = range(pa, pa+1);
auto bl = range(pb-1, pb);
auto br = range(pb, pb+1);
tree.range_add(al.first, al.second, -1);
tree.range_add(ar.first, ar.second, -1);
if (bl != ar) tree.range_add(bl.first, bl.second, -1);
if (br != al) tree.range_add(br.first, br.second, -1);
}
swap(pos[a], pos[b]);
swap(val[pa], val[pb]);
{
auto al = range(pa-1, pa);
auto ar = range(pa, pa+1);
auto bl = range(pb-1, pb);
auto br = range(pb, pb+1);
tree.range_add(al.first, al.second, 1);
tree.range_add(ar.first, ar.second, 1);
if (bl != ar) tree.range_add(bl.first, bl.second, 1);
if (br != al) tree.range_add(br.first, br.second, 1);
}
return tree.global_cnt();
}
#ifdef TEST
#include "grader.cpp"
#endif
