#include <bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int maxn = 2e6 + 10;
int n, h, w;
int rw[maxn], cw[maxn];
struct node
{
int minr, maxr, minc, maxc;
node(){};
node(int _minr, int _maxr, int _minc, int _maxc)
{
minr = _minr;
maxr = _maxr;
minc = _minc;
maxc = _maxc;
}
};
node t[maxn * 4];
node join(int i)
{
return node(min(t[2*i].minr, t[2*i+1].minr), max(t[2*i].maxr, t[2*i+1].maxr), min(t[2*i].minc, t[2*i+1].minc), max(t[2*i].maxc, t[2*i+1].maxc));
}
void build(int i, int l, int r)
{
if(l == r)
{
t[i] = node(rw[l], rw[l], cw[l], cw[l]);
return;
}
int mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
t[i] = join(i);
}
int updpos;
void update(int i, int l, int r)
{
if(l == r)
{
t[i] = node(rw[l], rw[l], cw[l], cw[l]);
return;
}
int mid = (l + r)/2;
if(updpos <= mid)update(2*i, l, mid);
else update(2*i+1, mid+1, r);
t[i] = join(i);
}
int ql, qr;
pair < int, int > queryrow(int i, int l, int r)
{
if(qr < l || ql > r)return make_pair(1e9, -1);
if(ql <= l && r <= qr)return make_pair(t[i].minr, t[i].maxr);
int mid = (l + r)/2;
pair < int, int > fh = queryrow(2*i, l, mid);
pair < int, int > sh = queryrow(2*i+1, mid+1, r);
return make_pair(min(fh.first, sh.first), max(fh.second, sh.second));
}
pair < int, int > querycol(int i, int l, int r)
{
if(qr < l || ql > r)return make_pair(1e9, -1);
if(ql <= l && r <= qr)return make_pair(t[i].minc, t[i].maxc);
int mid = (l + r)/2;
pair < int, int > fh = querycol(2*i, l, mid);
pair < int, int > sh = querycol(2*i+1, mid+1, r);
return make_pair(min(fh.first, sh.first), max(fh.second, sh.second));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
h = H;
w = W;
n = h * w;
for (int i = 0; i < n; ++ i)
{
rw[i] = R[i];
cw[i] = C[i];
}
build(1, 0, n-1);
// cout << "ans ids " << ans << endl;
}
int swap_seats(int a, int b)
{
swap(rw[a], rw[b]);
swap(cw[a], cw[b]);
updpos = a;
update(1, 0, n-1);
updpos = b;
update(1, 0, n-1);
int take = 0;
int minr = rw[0];
int maxr = rw[0];
int minc = cw[0];
int maxc = cw[0];
int ans = 0;
while(take < n)
{
//cout << take << endl;
int sum = (maxr - minr + 1)*(maxc - minc + 1);
if(sum == take + 1)
{
ans ++;
take ++;
}
else
{
take = sum - 1;
}
if(take == n)break;
ql = 0;
qr = take;
pair < int, int > rows = queryrow(1, 0, n-1);
pair < int, int > cols = querycol(1, 0, n-1);
minr = rows.first;
maxr = rows.second;
minc = cols.first;
maxc = cols.second;
}
assert(ans < (h + w)*10);
return ans;
}
