#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 minimo_r[1000000];
int maximo_r[1000000];
int minimo_c[1000000];
int maximo_c[1000000];
int ans = 1;
int segment_tree[4000000] = {};
bool beautiful[1000000] = {};
void change (ll i, ll minimo, ll maximo, ll x, ll valor)
{
if (minimo == maximo)
{
segment_tree[i] = valor;
return;
}
ll med = (minimo + maximo)/2;
if (x <= med)
change (2*i+1, minimo, med, x, valor);
else
change(2*i+2, med+1, maximo, x, valor);
segment_tree[i] = segment_tree[2*i+1] + segment_tree[2*i+2];
}
ll sum (ll i, ll minimo, ll maximo, ll menor, ll maior)
{
if (minimo == menor && maximo == maior)
return segment_tree[i];
ll med = (minimo + maximo)/2;
if (maior <= med)
return sum (2*i+1, minimo, med, menor, maior);
if (menor > med)
return sum (2*i+2, med+1, maximo, menor, maior);
return sum (2*i+1, minimo, med, menor, med) + sum (2*i+2, med+1, maximo, med+1, maior);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
r = R;
c = C;
h = H;
w = W;
minimo_r[0] = r[0];
maximo_r[0] = r[0];
minimo_c[0] = c[0];
maximo_c[0] = c[0];
beautiful[0] = 1;
REP(i, 1, H*W)
{
minimo_r[i] = min (minimo_r[i-1], r[i]);
maximo_r[i] = max (maximo_r[i-1], r[i]);
minimo_c[i] = min (minimo_c[i-1], c[i]);
maximo_c[i] = max (maximo_c[i-1], c[i]);
if ((maximo_r[i] - minimo_r[i] + 1)*(maximo_c[i] - minimo_c[i] + 1) == i+1)
{
ans ++;
beautiful[i] = 1;
}
}
}
int swap_seats(int a, int b)
{
if (a > b)
swap (a, b);
swap (r[a], r[b]);
swap (c[a], c[b]);
if (a == 0)
{
minimo_r[0] = r[0];
maximo_r[0] = r[0];
minimo_c[0] = c[0];
maximo_c[0] = c[0];
a++;
}
REP(i, a, b+1)
{
minimo_r[i] = min (minimo_r[i-1], r[i]);
maximo_r[i] = max (maximo_r[i-1], r[i]);
minimo_c[i] = min (minimo_c[i-1], c[i]);
maximo_c[i] = max (maximo_c[i-1], c[i]);
if ((maximo_r[i] - minimo_r[i] + 1)*(maximo_c[i] - minimo_c[i] + 1) == i+1)
{
if (!beautiful[i])
{
ans ++;
beautiful[i] = 1;
}
}
else
{
if (beautiful[i])
{
ans --;
beautiful[i] = 0;
}
}
}
return ans;
}
