#include "seats.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF = 1e9;
int h, w;
struct Point
{
int x, y;
};
struct SegmentTree
{
int tree[4*MAXN];
virtual int cmp(int x, int y)
{
assert(false);
}
virtual bool inSearch(int x, int y)
{
assert(false);
}
void build(int l, int r, int node, int vals[])
{
if (l == r)
{
tree[node] = vals[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node, vals);
build(mid + 1, r, 2*node + 1, vals);
tree[node] = cmp(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryPos, int queryVal)
{
if (l == r)
{
tree[node] = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = cmp(tree[2*node], tree[2*node + 1]);
}
int searchFirst(int l, int r, int node, int value)
{
if (l == r)
{
return l;
}
int mid = (l + r) / 2;
if (inSearch(tree[2*node], value)) return searchFirst(l, mid, 2*node, value);
return searchFirst(mid + 1, r, 2*node + 1, value);
}
void update(int pos, int val)
{
update(1, h * w, 1, pos, val);
}
int searchFirst(int value)
{
return searchFirst(1, h * w, 1, value);
}
void build(int vals[])
{
build(1, h * w, 1, vals);
}
};
struct SegmentTreeMAX : SegmentTree
{
int cmp(int x, int y) override
{
return std::max(x, y);
};
bool inSearch(int x, int y) override
{
return x > y;
};
};
struct SegmentTreeMIN : SegmentTree
{
int cmp(int x, int y)
{
return std::min(x, y);
}
bool inSearch(int x, int y)
{
return x < y;
}
};
Point p[MAXN];
int vals[MAXN];
int table[MAXN];
std::vector <int> t[MAXN];
SegmentTreeMIN minX, minY;
SegmentTreeMAX maxX, maxY;
void give_initial_chart(int H, int W, std::vector <int> R, std::vector <int> C)
{
h = H;
w = W;
for (int i = 0 ; i < H * W ; ++i)
{
p[i + 1] = {R[i] + 1, C[i] + 1};
table[R[i] * w + C[i]] = i + 1;
}
for (int i = 1 ; i <= h * w ; ++i)
{
vals[i] = p[i].x;
}
minX.build(vals);
maxX.build(vals);
for (int i = 1 ; i <= h * w ; ++i)
{
vals[i] = p[i].y;
}
minY.build(vals);
maxY.build(vals);
}
void fixPoint(int idx)
{
minX.update(idx, p[idx].x);
maxX.update(idx, p[idx].x);
minY.update(idx, p[idx].y);
maxY.update(idx, p[idx].y);
}
int swap_seats(int a, int b)
{
std::swap(p[table[a]], p[table[b]]);
std::swap(table[a], table[b]);
fixPoint(table[a]);
fixPoint(table[b]);
int ans = 1;
int minRow = p[1].x, minCol = p[1].y;
int maxRow = p[1].x, maxCol = p[1].y;
int sz = 1;
while (sz < h * w)
{
int firstMinX = minX.searchFirst(minRow);
int firstMaxX = maxX.searchFirst(maxRow);
int firstMinY = minY.searchFirst(minCol);
int firstMaxY = maxY.searchFirst(maxCol);
int first = std::min(std::min(firstMinX, firstMaxX), std::min(firstMinY, firstMaxY));
// std::cout << "here: " << minRow << ' ' << minCol << ' ' << maxRow << ' ' << maxCol << ' ' << first << ' ' << sz << '\n';
if (first == sz + 1)
{
ans++;
}
minRow = std::min(minRow, p[first].x);
maxRow = std::max(maxRow, p[first].x);
minCol = std::min(minCol, p[first].y);
maxCol = std::max(maxCol, p[first].y);
sz = (maxRow - minRow + 1) * (maxCol - minCol + 1);
}
return ans;
}
