#include <bits/stdc++.h>
#include "seats.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3+10;
int n, m;
vector<int> x, y;
struct Node
{
int mn_x, mx_x, mn_y, mx_y;
};
struct SegmentTree
{
Node tree[4*1000010];
void combine(int node)
{
tree[node].mn_x = min(tree[2*node].mn_x, tree[2*node+1].mn_x);
tree[node].mx_x = max(tree[2*node].mx_x, tree[2*node+1].mx_x);
tree[node].mn_y = min(tree[2*node].mn_y, tree[2*node+1].mn_y);
tree[node].mx_y = max(tree[2*node].mx_y, tree[2*node+1].mx_y);
}
void build(int node, int l, int r)
{
if (l == r)
{
tree[node] = {x[l], x[l], y[l], y[l]};
return;
}
int mid = (l+r)>>1;
build(2*node, l, mid); build(2*node+1, mid+1, r);
combine(node);
}
void upd(int node, int l, int r, int pos, int vx, int vy)
{
if (l == r)
{
tree[node] = {vx, vx, vy, vy};
return;
}
int mid = (l+r)>>1;
if (pos <= mid) upd(2*node, l, mid, pos, vx, vy);
else upd(2*node+1, mid+1, r, pos, vx, vy);
combine(node);
}
Node query(int node, int l, int r, int a, int b)
{
if (l > b || r < a) return {n*m, 0, n*m, 0};
if (l >= a && r <= b) return tree[node];
int mid = (l+r)>>1;
Node p1 = query(2*node, l, mid, a, b);
Node p2 = query(2*node+1, mid+1, r, a, b);
return {min(p1.mn_x, p2.mn_x), max(p1.mx_x, p2.mx_x), min(p1.mn_y, p2.mn_y), max(p1.mx_y, p2.mx_y)};
}
} seg;
bool ok[1000010];
int tot;
bool flag;
int sub_1(void)
{
flag = 0;
int mn_x = x[0], mx_x = x[0];
int mn_y = y[0], mx_y = y[0];
int ans = 1;
ok[0] = 1;
for (int i = 1; i < n*m; i++)
{
mn_x = min(mn_x, x[i]); mx_x = max(mx_x, x[i]);
mn_y = min(mn_y, y[i]); mx_y = max(mx_y, y[i]);
if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1) ans++, ok[i] = 1;
}
return ans;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H, m = W;
for (int i = 0; i < n*m; i++)
{
x.push_back(R[i]);
y.push_back(C[i]);
}
seg.build(1, 0, n*m-1);
tot = sub_1();
flag = 1;
}
int sub_2(void)
{
flag = 0;
int ans = 0;
for (int i = 0; i < n*m; )
{
Node node = seg.query(1, 0, n*m-1, 0, i);
int mn_x = node.mn_x, mx_x = node.mx_x, mn_y = node.mn_y, mx_y = node.mx_y;
if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1) ans++;
i = max(i+1, (mx_x-mn_x+1)*(mx_y-mn_y+1)-1);
}
return ans;
}
int sub_3(int a, int b)
{
if (a > b) swap(a, b);
Node node = seg.query(1, 0, n*m-1, 0, a);
int mn_x = node.mn_x, mx_x = node.mx_x, mn_y = node.mn_y, mx_y = node.mx_y;
for (int i = a; i < b; i++)
{
tot -= ok[i];
mn_x = min(mn_x, x[i]); mx_x = max(mx_x, x[i]);
mn_y = min(mn_y, y[i]); mx_y = max(mx_y, y[i]);
if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1)
{
tot++;
ok[i] = 1;
}
else ok[i] = 0;
}
return tot;
}
int swap_seats(int a, int b)
{
int xa = x[a], ya = y[a];
int xb = x[b], yb = y[b];
x[a] = xb, y[a] = yb;
x[b] = xa, y[b] = ya;
seg.upd(1, 0, n*m-1, a, x[a], y[a]); seg.upd(1, 0, n*m-1, b, x[b], y[b]);
if (n <= 1000 && m <= 1000) return sub_2();
if (flag && abs(a-b) <= 10000) return sub_3(a, b);
return sub_1();
}
