#include "seats.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int N = (int)1e6 + 6;
const int INF = 0x3f3f3f3f;
int pos[N], arr[N];
int n;
struct node {
int mn, cnt;
node(int x) {
mn = x, cnt = 1;
}
node() {
mn = INF, cnt = 0;
}
node operator + (const node& other) {
node res;
res.mn = min(mn, other.mn);
res.cnt = 0;
if (res.mn == mn) res.cnt += cnt;
if (res.mn == other.mn) res.cnt += other.cnt;
return res;
}
};
node tree[4 * N];
int add[4 * N];
void push(int v, int tl, int tr) {
if (add[v] == 0) {
return;
}
tree[v].mn += add[v];
if (tl != tr) {
add[v + v + 1] += add[v];
add[v + v + 2] += add[v];
}
add[v] = 0;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = node(tl);
//cout << tl << ": " << tree[v].mn << " " << tree[v].cnt << endl;
return;
}
int mid = (tl + tr) >> 1;
build(v + v + 1, tl, mid);
build(v + v + 2, mid + 1, tr);
tree[v] = tree[v + v + 1] + tree[v + v + 2];
}
void upd(int ql, int qr, int val, int v, int tl, int tr) {
push(v, tl, tr);
if (ql > tr || tl > qr) {
return;
}
if (ql <= tl && tr <= qr) {
add[v] += val;
push(v, tl, tr);
return;
}
int mid = (tl + tr) >> 1;
upd(ql, qr, val, v + v + 1, tl, mid);
upd(ql, qr, val, v + v + 2, mid + 1, tr);
tree[v] = tree[v + v + 1] + tree[v + v + 2];
}
int get(int pos, int v, int tl, int tr) {
push(v, tl, tr);
if (tl == tr) {
return tree[v].mn;
}
int mid = (tl + tr) >> 1;
if (pos <= mid) {
return get(pos, v + v + 1, tl, mid);
}
else {
return get(pos, v + v + 2, mid + 1, tr);
}
}
void see() {
for (int i = 0; i < n; i++) {
cout << get(i, 0, 0, n - 1) << " ";
}cout << endl;
}
void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
assert(H == 1);
n = W;
for (int i = 0; i < n; i++) {
pos[i] = C[i];
}
for (int i = 0; i < n; i++) {
arr[pos[i]] = i;
}
build(0, 0, n - 1);
//puts("arr");
//for (int i = 0; i < n; i++) {
// cout << arr[i] << " ";
//}cout << "\n\n";
//puts("tree");
//for (int i = 0; i < n; i++) {
// cout << get(i, 0, 0, n - 1) << " ";
//}cout << "\n\n";
for (int i = 0; i + 1 < n; i++) {
int mx = max(arr[i], arr[i + 1]);
upd(mx, n - 1, -1, 0, 0, n - 1);
}
}
int swap_seats(int a, int b) {
set <pair<int, int>> go;
if (a > 0) {
go.insert({ a - 1, a });
}
if (a + 1 < n) {
go.insert({ a, a + 1 });
}
if (b > 0) {
go.insert({ b - 1, b });
}
if (a + 1 < n) {
go.insert({ a, a + 1 });
}
for (pii pr : go) {
int mx = max(arr[pr.fr], arr[pr.sc]);
upd(mx, n - 1, 1, 0, 0, n - 1);
}
swap(arr[pos[a]], arr[pos[b]]);
swap(pos[a], pos[b]);
for (pii pr : go) {
int mx = max(arr[pr.fr], arr[pr.sc]);
upd(mx, n - 1, -1, 0, 0, n - 1);
}
return tree[0].cnt;
}
//signed main() {
// int N, M, Q;
// cin >> N >> M >> Q;
// vector <int> my;
// my.resize(M);
// for (int& el : my) {
// cin >> el;
// }
// vector <int> R, C;
// R.resize(N * M);
// C.resize(N * M);
// for (int i = 0; i < M; i++) {
// R[my[i]] = 0;
// C[my[i]] = i;
// }
// give_initial_chart(N, M, R, C);
// cout << "answer: " << swap_seats(0, 0) << endl;
//}
