#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
const int maxn = 1000005;
const int INF = INT_MAX - 1;
int jo[maxn];
struct Elem {
int h_max, h_min;
int w_max, w_min;
bool ures;
Elem() {
ures = true;
h_max = -1;
h_min = INF;
w_max = -1;
w_min = INF;
}
Elem(int x, int y) {
ures = false;
h_max = x;
h_min = x;
w_max = y;
w_min = y;
}
void rep(Elem a, Elem b) {
ures = a.ures && b.ures;
h_max = max(a.h_max,b.h_max);
h_min = min(a.h_min,b.h_min);
w_max = max(a.w_max,b.w_max);
w_min = min(a.w_min,b.w_min);
}
int get_size() {
if(ures) return 0;
return (h_max - h_min + 1) * (w_max - w_min + 1);
}
};
Elem fa[maxn*8];
void epit(int hol, int tol, int ig, vector<int> &R, vector<int> &C) {
if(tol == ig) {
fa[hol] = Elem(R[tol],C[tol]);
return;
}
int mid = (tol + ig) / 2;
epit(hol*2,tol,mid,R,C);
epit(hol*2+1,mid+1,ig,R,C);
fa[hol].rep(fa[hol*2],fa[hol*2+1]);
return;
}
Elem ask(int hol, int tol, int ig, int to) {
if(ig <= to) {
return fa[hol];
}
Elem uj;
if(to < tol) {
return uj;
}
int mid = (tol + ig) / 2;
uj.rep(ask(hol*2,tol,mid,to),ask(hol*2+1,mid+1,ig,to));
return uj;
}
void modif(int hol, int tol, int ig, int poz, Elem &val) {
if(tol == ig) {
fa[hol] = val;
return;
}
int mid = (tol + ig) / 2;
if(poz <= mid) {
modif(hol*2,tol,mid,poz,val);
}
else {
modif(hol*2+1,mid+1,ig,poz,val);
}
fa[hol].rep(fa[hol*2],fa[hol*2+1]);
return;
}
int szep = 0;
vector<int> R, C;
int N;
void give_initial_chart(int H, int W, vector<int> RR, vector<int> CC) {
R = RR;
C = CC;
N = H * W;
epit(1,0,N-1,R,C);
for(int i=0;i<N;i++) {
if(ask(1,0,N-1,i).get_size() == i+1) {
szep++;
jo[i] = 1;
}
}
return;
}
int swap_seats(int a, int b) {
swap(R[a],R[b]);
swap(C[a],C[b]);
Elem A(R[a],C[a]);
Elem B(R[b],C[b]);
modif(1,0,N-1,a,A);
modif(1,0,N-1,b,B);
Elem r = ask(1,0,N-1,min(a,b));
for(int i=min(a,b);i<max(a,b);i++) {
szep -= jo[i];
jo[i] = 0;
if(r.get_size() == i+1) {
jo[i] = 1;
}
szep += jo[i];
Elem U(R[i+1],C[i+1]);
r.rep(r,U);
}
return szep;
}
