#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define REP(i, a, b) for (ll i=a; i<b; i++)
std::vector<int> r;
std::vector<int> c;
int h, w;
int segment_tree[4000000][4] = {};
set<int> beautiful;
void create (ll i, ll minimo, ll maximo)
{
if (minimo == maximo)
{
segment_tree[i][0] = r[minimo];
segment_tree[i][1] = r[minimo];
segment_tree[i][2] = c[minimo];
segment_tree[i][3] = c[minimo];
return;
}
ll med = (minimo + maximo)/2;
create (2*i+1, minimo, med);
create (2*i+2, med+1, maximo);
segment_tree[i][0] = min (segment_tree[2*i+1][0], segment_tree[2*i+2][0]);
segment_tree[i][1] = max (segment_tree[2*i+1][1], segment_tree[2*i+2][1]);
segment_tree[i][2] = min (segment_tree[2*i+1][2], segment_tree[2*i+2][2]);
segment_tree[i][3] = max (segment_tree[2*i+1][3], segment_tree[2*i+2][3]);
return;
}
void change (ll i, ll minimo, ll maximo, ll x, ll valor, ll type)
{
if (minimo == maximo)
{
segment_tree[i][type] = valor;
return;
}
ll med = (minimo + maximo)/2;
if (x <= med)
change (2*i+1, minimo, med, x, valor, type);
else
change(2*i+2, med+1, maximo, x, valor, type);
if (type%2 == 0)
segment_tree[i][type] = min(segment_tree[2*i+1][type], segment_tree[2*i+2][type]);
else
segment_tree[i][type] = max(segment_tree[2*i+1][type], segment_tree[2*i+2][type]);
}
ll intervalo (ll i, ll minimo, ll maximo, ll menor, ll maior, ll type)
{
if (minimo == menor && maximo == maior)
return segment_tree[i][type];
ll med = (minimo + maximo)/2;
if (maior <= med)
return intervalo (2*i+1, minimo, med, menor, maior, type);
if (menor > med)
return intervalo (2*i+2, med+1, maximo, menor, maior, type);
if (type%2 == 0)
return min (intervalo (2*i+1, minimo, med, menor, med, type), intervalo(2*i+2, med+1, maximo, med+1, maior, type));
else
return max (intervalo (2*i+1, minimo, med, menor, med, type), intervalo(2*i+2, med+1, maximo, med+1, maior, type));
}
ll minimo_r (ll a)
{
return intervalo(0, 0, h*w-1, 0, a, 0);
}
ll maximo_r (ll a)
{
return intervalo(0, 0, h*w-1, 0, a, 1);
}
ll minimo_c (ll a)
{
return intervalo(0, 0, h*w-1, 0, a, 2);
}
ll maximo_c (ll a)
{
return intervalo(0, 0, h*w-1, 0, a, 3);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
r = R;
c = C;
h = H;
w = W;
create (0, 0, h*w-1);
ll iterador = 0;
while (iterador < h*w)
{
int maior_c = maximo_c(iterador);
int menor_c = minimo_c(iterador);
int maior_r = maximo_r(iterador);
int menor_r = minimo_r (iterador);
if ((maior_c - menor_c + 1)*(maior_r - menor_r + 1) == iterador + 1)
{
beautiful.insert (iterador);
if (iterador == h*w-1)
break;
maior_c = max (maior_c, c[iterador+1]);
menor_c = min (menor_c, c[iterador+1]);
maior_r = max (maior_r, r[iterador+1]);
menor_r = min (menor_r, r[iterador+1]);
}
iterador = (maior_c - menor_c + 1)*(maior_r - menor_r + 1) - 1;
}
return;
}
int swap_seats(int a, int b)
{
if (a > b)
swap (a, b);
change(0, 0, h*w-1, a, r[b], 0);
change(0, 0, h*w-1, a, r[b], 1);
change(0, 0, h*w-1, a, c[b], 2);
change(0, 0, h*w-1, a, c[b], 3);
change(0, 0, h*w-1, b, r[a], 0);
change(0, 0, h*w-1, b, r[a], 1);
change(0, 0, h*w-1, b, c[a], 2);
change(0, 0, h*w-1, b, c[a], 3);
swap (r[a], r[b]);
swap (c[a], c[b]);
beautiful.erase (beautiful.lower_bound(a), beautiful.lower_bound(b));
ll iterador = a;
while (iterador <= b)
{
int maior_c = maximo_c(iterador);
int menor_c = minimo_c(iterador);
int maior_r = maximo_r(iterador);
int menor_r = minimo_r (iterador);
if ((maior_c - menor_c + 1)*(maior_r - menor_r + 1) == iterador + 1)
{
beautiful.insert (iterador);
if (iterador == h*w-1)
break;
maior_c = max (maior_c, c[iterador+1]);
menor_c = min (menor_c, c[iterador+1]);
maior_r = max (maior_r, r[iterador+1]);
menor_r = min (menor_r, r[iterador+1]);
}
iterador = (maior_c - menor_c + 1)*(maior_r - menor_r + 1) - 1;
}
return beautiful.size();
}
