#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+3;
vector<vector<int> > matriz;
pair<int, int> wh[MAXN];
vector<vector<int> > seg;
int sg[MAXN*4][4];
int n, m, respf;
void buildm(int sind, int ini, int fim, int i, int k) {
if(ini==fim) {
seg[k][sind]=matriz[i][ini];
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
buildm(e, ini, mid, i, k);
buildm(d, mid+1, fim, i, k);
seg[k][sind]=max(seg[k][e], seg[k][d]);
}
void buildn(int sind, int ini, int fim) {
if(ini==fim) {
seg[sind].resize(m*4+3);
buildm(1, 0, m-1, ini, sind);
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
buildn(e, ini, mid);
buildn(d, mid+1, fim);
seg[sind]=seg[e];
for(int i=0; i<seg[sind].size(); i++) seg[sind][i]=max(seg[sind][i], seg[d][i]);
}
void updatem(int sind, int ini, int fim, int i, int j, int k) {
if(ini==fim) {
seg[k][sind]=matriz[i][j];
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
if(j<=mid) updatem(e, ini, mid, i, j, k);
else updatem(d, mid+1, fim, i, j, k);
seg[k][sind]=max(seg[k][e], seg[k][d]);
}
void remerge2d(int sind, int ini, int fim, int ind, int k) {
seg[k][sind]=max(seg[k*2][sind], seg[k*2+1][sind]);
if(ini==fim) return;
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
if(ind<=mid) remerge2d(e, ini, mid, ind, k);
else remerge2d(d, mid+1, fim, ind, k);
}
void updaten(int sind, int ini, int fim, int i, int j) {
if(ini==fim) {
updatem(1, 0, m-1, i, j, sind);
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
if(i<=mid) updaten(e, ini, mid, i, j);
else updaten(d, mid+1, fim, i, j);
remerge2d(1, 0, m-1, j, sind); //ERRO!!?
}
int querym(int sind, int ini, int fim, int qini, int qfim, int k) {
if(qfim<ini||qini>fim) return 0;
if(qini<=ini&&qfim>=fim) return seg[k][sind];
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
return max(querym(e, ini, mid, qini, qfim, k), querym(d, mid+1, fim, qini, qfim, k));
}
int queryn(int sind, int ini, int fim, int nl, int nr, int ml, int mr) {
if(nr<ini||nl>fim) return 0;
if(nl<=ini&&nr>=fim) return querym(1, 0, m-1, ml, mr, sind);
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
return max(queryn(e, ini, mid, nl, nr, ml, mr), queryn(d, mid+1, fim, nl, nr, ml, mr));
}
void remerge(int sind, int e, int d) {
for(int i=0; i<4; i++) {
if(i&1) sg[sind][i]=max(sg[e][i], sg[d][i]);
else sg[sind][i]=min(sg[e][i], sg[d][i]);
}
}
void build(int sind, int ini, int fim) {
if(ini==fim) {
sg[sind][0]=sg[sind][1]=wh[ini].first;
sg[sind][2]=sg[sind][3]=wh[ini].second;
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
build(e, ini, mid);
build(d, mid+1, fim);
remerge(sind, e, d);
}
void update(int sind, int ini, int fim, int qind) {
if(ini==fim) {
sg[sind][0]=sg[sind][1]=wh[ini].first;
sg[sind][2]=sg[sind][3]=wh[ini].second;
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
if(qind<=mid) update(e, ini, mid, qind);
else update(d, mid+1, fim, qind);
remerge(sind, e, d);
}
void query(int sind, int ini, int fim, int qind) {
if(sind==1) {
sg[0][0]=sg[0][2]=MAXN*2;
sg[0][1]=sg[0][3]=-1;
}
if(qind>=fim) {
remerge(0, 0, sind);
return;
}
int e=sind*2; int d=e+1;
int mid=(ini+fim)>>1;
query(e, ini, mid, qind);
if(qind>mid) query(d, mid+1, fim, qind);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n=H; m=W;
matriz.resize(n); for(int i=0; i<n; i++) matriz[i].resize(m);
for(int i=0; i<n*m; i++) {
wh[i]={R[i], C[i]};
matriz[R[i]][C[i]]=i;
}
seg.resize(n*4+3);
buildn(1, 0, n-1);
build(1, 0, n*m-1);
for(int i=0; i<n*m; i++) {
query(1, 0, n*m-1, i);
int tam=sg[0][1]-sg[0][0]+1;
tam*=(sg[0][3]-sg[0][2]+1);
// printf("%d > %d // %d %d %d %d\n", i+1, tam, sg[0][0], sg[0][1], sg[0][2], sg[0][3]);
if(tam==i+1) respf++;
}
}
void revert(int a, int b, int k) {
int tam, p=a;
while(p<=b) {
query(1, 0, n*m-1, p);
tam=sg[0][1]-sg[0][0]+1;
tam*=(sg[0][3]-sg[0][2]+1);
// printf("%d > %d // %d %d %d %d\n", p+1, tam, sg[0][0], sg[0][1], sg[0][2], sg[0][3]);
if(tam-1==p) {
respf+=k;
p++;
}
else {
p=queryn(1, 0, n-1, sg[0][0], sg[0][1], sg[0][2], sg[0][3]);
}
}
}
int swap_seats(int a, int b) {
if(a>b) swap(a, b);
//unmount
revert(a, b, -1);
swap(wh[a], wh[b]);
matriz[wh[a].first][wh[a].second]=a;
matriz[wh[b].first][wh[b].second]=b;
update(1, 0, n*m-1, a);
update(1, 0, n*m-1, b);
updaten(1, 0, n-1, wh[a].first, wh[a].second);
updaten(1, 0, n-1, wh[b].first, wh[b].second);
//mount
revert(a, b, 1);
return respf;
}
