#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
std::vector<int> r;
vector<int> c;
int h, w;
const int N = 1000000;
int tree[4 * N][2][2];
const int MA = 2000000000;
void ins(int num, int i, int a, int b, int node, int typ)
{
if (a == b)
{
tree[node][typ][0] = num;
tree[node][typ][1] = num;
return;
}
int mid = (a + b) / 2;
if (i <= mid) ins(num, i, a, mid, node * 2, typ);
if (i > mid) ins(num, i, mid + 1, b, node * 2 + 1, typ);
tree[node][typ][0] = min(tree[node * 2][typ][0], tree[node * 2 + 1][typ][0]);
tree[node][typ][1] = max(tree[node * 2][typ][1], tree[node * 2 + 1][typ][1]);
}
int firstWith(int diff, int a, int b, int cmin, int cmax, int node, int typ)
{
if (a == b)
{
if (abs(max(cmax, tree[node][typ][1]) - min(cmin, tree[node][typ][0])) == diff) return a;
else return -1;
}
int mid = (a + b) / 2;
if (abs(max(cmax, tree[node * 2][typ][1]) - min(cmin, tree[node * 2][typ][0])) >= diff) return firstWith(diff, a, mid, cmin, cmax, node * 2, typ);
cmin = min(cmin, tree[node * 2][typ][0]);
cmax = max(cmax, tree[node * 2][typ][1]);
return firstWith(diff, mid + 1, b, cmin, cmax, node * 2+ 1, typ);
}
void getDiff(int to, int a, int b, int& cmin, int& cmax, int node, int typ)
{
if (to >= b)
{
cmin = min(tree[node][typ][0], cmin);
cmax = max(cmax, tree[node][typ][1]);
return;
}
int mid = (a + b) / 2;
getDiff(to, a, mid, cmin, cmax, node * 2, typ);
if (to > mid) getDiff(to, mid + 1, b, cmin, cmax, node * 2 + 1, typ);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
h = H;
w = W;
for (int i = 0; i< h * w; i++)
{
ins(r[i], i, 0, h * w - 1, 1, 0);
}
for (int i = 0; i< h * w; i++)
{
ins(c[i], i, 0, h * w - 1, 1, 1);
}
}
bool isGood(int i)
{
int amin = MA;
int amax = -1;
getDiff(i, 0, h * w - 1, amin, amax, 1, 0);
int a = abs(amax - amin + 1);
int bmin = MA;
int bmax = -1;
getDiff(i, 0, h * w - 1, bmin, bmax, 1, 1);
int b = abs(bmax - bmin + 1);
return (i + 1) == a * b;
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
if (h * w <= 10000)
{
int res = 0;
int hmin = MA;
int hmax = -1;
int cmin = MA;
int cmax = -1;
for (int i = 0; i < h * w; i++)
{
hmin = min(hmin, r[i]);
cmin = min(cmin, c[i]);
hmax = max(hmax, r[i]);
cmax = max(cmax, c[i]);
if (i == (hmax - hmin + 1) * (cmax - cmin + 1) - 1) res++;
}
return res;
}
ins(r[a], a, 0, h * w - 1, 1, 0);
ins(c[a], a, 0, h * w - 1, 1, 1);
ins(r[b], b, 0, h * w - 1, 1, 0);
ins(c[b], b, 0, h * w - 1, 1, 1);
vector<array<int, 3>> byH;
vector<array<int, 3>> byW;
int last = 0;
int cval = 0;
for (int i = 1; i < h; i++)
{
int nxt = firstWith(i, 0, h * w - 1, MA, -1, 1, 0);
if (nxt != -1)
{
byH.push_back({last, nxt - 1, cval});
cval = i;
last = nxt;
}
}
byH.push_back({last, h * w - 1, cval});
last = 0;
cval = 0;
for (int i = 1; i < w; i++)
{
int nxt = firstWith(i, 0, h * w - 1, MA, -1, 1, 1);
if (nxt != -1)
{
byW.push_back({last, nxt - 1, cval});
last = nxt;
cval = i;
}
}
byW.push_back({last, h * w - 1, cval});
int ch = 0;
int cw = 0;
set<int> good;
while (ch < byH.size())
{
while (cw < byW.size() && byW[cw][0] <= byH[ch][1])
{
int cur = ((byH[ch][2] + 1) * (byW[cw][2] + 1) - 1);
if (cur >= byW[cw][0] && cur <= byW[cw][1] && cur >= byH[ch][0] && cur <= byH[ch][1]) good.insert((byH[ch][2] + 1) * (byW[cw][2] + 1) - 1);
if (byW[cw][1] > byH[ch][1]) break;
cw++;
}
ch++;
}
return good.size();
}
/*
1 5 1
0 0
0 1
0 2
0 3
0 4
0 4
*/
