#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
//#define int long long
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
int H, W;
const int mxh = 1e4, mxw = 1e4;
pii coord[10000];
// PREFIX BOUNDING BOX SEGTREE
const pair<pii, pii> defval = {{1e18, 1e18}, {-1e18, -1e18}}; // tl min br max
pair<pii, pii> seg[4 * 10000];
pair<pii, pii> segfunction(pair<pii, pii> x, pair<pii, pii> y) {
return {{min(x.fi.fi, y.fi.fi), min(x.fi.se, y.fi.se)}, {max(x.se.fi, y.se.fi), max(x.se.se, y.se.se)}};
}
pair<pii, pii> query(int l, int r, int pos, int ql, int qr) {
if (ql > r || l > qr) {
return defval;
}
if (ql <= l && r <= qr) {
return seg[pos];
}
int mid = (l + r) / 2;
return segfunction(query(l, mid, pos * 2, ql, qr), query(mid + 1, r, pos * 2 + 1, ql, qr));
}
void build(int l, int r, int pos) {
if (l == r) {
seg[pos] = {coord[l], coord[l]};
return;
}
int mid = (l + r) / 2;
build(l, mid, pos * 2);
build(mid + 1, r, pos * 2 + 1);
seg[pos] = segfunction(seg[pos * 2], seg[pos * 2 + 1]);
}
void update(int l, int r, int pos, int qpos, pii qval) {
if (l == r) {
seg[pos] = {qval, qval};
return;
}
int mid = (l + r) / 2;
if (qpos <= mid) {
update(l, mid, pos * 2, qpos, qval);
} else {
update(mid + 1, r, pos * 2 + 1, qpos, qval);
}
seg[pos] = segfunction(seg[pos * 2], seg[pos * 2 + 1]);
}
// ANSWER SEGTREE
const int defval1 = 0;
int seg1[4 * 10000];
int segfunction1(int x, int y) {
return x + y;
}
int query1(int l, int r, int pos, int ql, int qr) {
if (ql > r || l > qr) {
return defval1;
}
if (ql <= l && r <= qr) {
return seg1[pos];
}
int mid = (l + r) / 2;
return segfunction1(query1(l, mid, pos * 2, ql, qr), query1(mid + 1, r, pos * 2 + 1, ql, qr));
}
void update1(int l, int r, int pos, int qpos, int qval) {
if (l == r) {
seg1[pos] = qval;
return;
}
int mid = (l + r) / 2;
if (qpos <= mid) {
update1(l, mid, pos * 2, qpos, qval);
} else {
update1(mid + 1, r, pos * 2 + 1, qpos, qval);
}
seg1[pos] = segfunction1(seg1[pos * 2], seg1[pos * 2 + 1]);
}
void give_initial_chart(int H1, int W1, vi R, vi C) {
H = H1; W = W1;
for (int i = 0; i < H * W; i++) {
coord[i] = {R[i], C[i]};
}
build(0, H*W - 1, 1);
for (int i = 0; i < H * W; i++) {
pair<pii, pii> bound = query(0, H*W - 1, 1, 0, i);
pii tl = bound.fi, br = bound.se;
int ans = ((br.fi - tl.fi + 1) * (br.se - tl.se + 1) == (i + 1));
//cout << i << ": tl->{" << bound.fi.fi << " " << bound.fi.se << "} br->{" << bound.se.fi << " " << bound.se.se << "}\n";
update1(0, H*W - 1, 1, i, ans);
}
}
int swap_seats(int a, int b) {
swap(coord[a], coord[b]);
update(0, H*W - 1, 1, a, coord[a]);
update(0, H*W - 1, 1, b, coord[b]);
for (int i = a; i <= b; i++) {
pair<pii, pii> bound = query(0, H*W - 1, 1, 0, i);
pii tl = bound.fi, br = bound.se;
int ans = ((br.fi - tl.fi + 1) * (br.se - tl.se + 1) == (i + 1));
update1(0, H*W - 1, 1, i, ans);
}
return query1(0, H*W - 1, 1, 0, H*W - 1);
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
