#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;
struct subtask3 {
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];
int pos[N], arr[N];
int 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);
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 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);
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 (pos[a] > 0) {
go.insert({ pos[a] - 1, pos[a] });
}
if (pos[a] + 1 < n) {
go.insert({ pos[a], pos[a] + 1 });
}
if (pos[b] > 0) {
go.insert({ pos[b] - 1, pos[b] });
}
if (pos[b] + 1 < n) {
go.insert({ pos[b], pos[b] + 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;
}
} solve;
void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
solve.give_initial_chart(H, W, R, C);
}
int swap_seats(int a, int b) {
return solve.swap_seats(a, b);
}
//signed main() {
// int N, M, Q;
// cin >> N >> M >> Q;
// vector <int> R, C;
// vector <int> my;
// my.resize(N * M);
// R.resize(N * M);
// C.resize(N * M);
// for (int i = 0; i < M; i++) {
// cin >> my[i];
// }
// for (int i = 0; i < M; i++) {
// R[my[i]] = 0;
// C[my[i]] = i;
// }
// give_initial_chart(N, M, R, C);
//
// while (Q--) {
// int a, b;
// cin >> a >> b;
// cout << swap_seats(a, b) << endl;
// }
//}
/*
1 5 1
0 1 3 4 2
4 3
*/
