//~ #include "seats.h"
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define fort(i,n) for(int i=0;i<=(int)n;++i)
#define fori(i,a,n) for(int i=a;i<(int)n;++i)
#define forit(i,a,n) for(int i=a;i<=(int)n;++i)
#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
using namespace std;
template<typename T>
ostream &operator<<(ostream &os, vector<T> v){
os<<"[";
forn(i,SZ(v)){
if(i) os<<", ";
os<<v[i];
}
os<<"]";
return os;
}
const int INF = 1000005;
struct ST{
struct Node{
int mn=0;
int qt=0;
};
int n;
vector<int> mn;
vector<int> qt;
vector<int> lz;
vector<int> bk;
void init(int _n){
n=1<<(32-__builtin_clz(_n-1));
mn.resize(2*n-1);
qt.resize(2*n-1);
lz.resize(2*n-1);
bk.resize(2*n-1);
fori(i,n-1,2*n-1) qt[i] = 1;
for(int i=n-2;i>=0;--i) merge(i);
}
void push(int i){
if(!lz[i]) return;
mn[i] += lz[i];
if(i<n-1){
lz[2*i+1] += lz[i];
lz[2*i+2] += lz[i];
}
lz[i] = 0;
}
void split(int i){
if(bk[i]){
bk[2*i+1] += bk[i];
bk[2*i+2] += bk[i];
bk[i] = 0;
}
}
Node merge(const Node &a, const Node &b){
if(a.mn < b.mn) return a;
if(b.mn < a.mn) return b;
return {a.mn, a.qt + b.qt};
}
void merge(int i){ // en teoría los hijos ya pushearon
int l=2*i+1, r=2*i+2;
int x = min(bk[l], bk[r]);
bk[l] -= x;
bk[r] -= x;
bk[i] += x; // une los segmentos
assert(bk[l] == 0 || bk[r] == 0);
// no puede ocurrir el caso en el que ambos están bloqueados
if(!bk[l] && (mn[l] < mn[r] || bk[r])){
mn[i] = mn[l];
qt[i] = qt[l];
} else if(!bk[r] && (mn[r] < mn[l] || bk[l])){
mn[i] = mn[r];
qt[i] = qt[r];
} else if(mn[l] == mn[r]){
mn[i] = mn[l];
qt[i] = qt[l]+qt[r];
} else{
//~ DBG4(bk[l], mn[l], bk[r], mn[r]);
assert(0);
}
}
void update(int ul, int ur, int v, int l, int r, int i){
push(i);
if(l>=ur||r<=ul) return;
if(l>=ul&&r<=ur){
lz[i] += v;
push(i);
return;
}
int m=(l+r)/2;
update(ul,ur,v,l,m,2*i+1);
update(ul,ur,v,m,r,2*i+2);
merge(i);
}
void update(int l, int r, int v){
update(l,r,v,0,n,0);
}
void block(int ul, int ur, int v, int l, int r, int i){
push(i);
if(l>=ur||r<=ul) return;
if(l>=ul&&r<=ur){
bk[i] += v;
return;
}
int m=(l+r)/2;
split(i); // creo que no hace falta en el update
block(ul,ur,v,l,m,2*i+1);
block(ul,ur,v,m,r,2*i+2);
merge(i);
}
void block(int l, int r, int v){
block(l,r,v,0,n,0);
}
Node query(int ql, int qr, int l, int r, int i){
push(i);
//~ DBG4("entra", l, r, i);
if(l>=qr||r<=ql) return {INF, 0};
if(l>=ql&&r<=qr){
Node aux = {mn[i], qt[i]};
if(bk[i]) aux = {INF,0};
//~ DBG3(i, aux.mn, aux.qt);
return aux;
}
int m = (l+r)/2;
Node aux = merge(query(ql,qr,l,m,2*i+1),query(ql,qr,m,r,2*i+2));
if(bk[i]){
//~ DBG("entra aca");
aux.mn = INF;
aux.qt = 0;
}
//~ DBG3(i, aux.mn, aux.qt);
return aux;
}
int query(int l, int r){
Node aux = query(l,r,0,n,0);
assert(aux.mn == 4); // siempre está presente porque es la totalidad
return aux.qt;
}
void print(ostream &os, int i, bool b){
push(i);
b = b || bk[i];
if(i>=n-1){
os<<"("<<(b?-1*mn[i]:mn[i])<<","<<qt[i]<<") ";
return;
}
print(os,2*i+1,b);
print(os,2*i+2,b);
}
void print(ostream &os){
print(os,0,0);
os<<endl<<mn<<endl;
}
} corners;
ostream &operator<<(ostream &os, ST &st){
st.print(os);
return os;
}
struct P{
int r, c;
};
int n;
vector<vector<int>> seats;
vector<P> pos;
void process(int r, int c, int v){
vector<int> s;
s.push_back(seats[r][c]);
s.push_back(seats[r][c+1]);
s.push_back(seats[r+1][c]);
s.push_back(seats[r+1][c+1]);
sort(ALL(s));
corners.update(s[0],s[1],v);
corners.block(s[2],s[3],v);
}
void add(int r, int c){
process(r,c,+1);
}
void rem(int r, int c){
process(r,c,-1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H*W;
seats.resize(H+2, vector<int>(W+2,n));
pos.resize(n);
forn(i,n){
int r=R[i]+1;
int c=C[i]+1;
seats[r][c] = i;
pos[i] = {r, c};
}
corners.init(n+1);
fort(i,H) fort(j,W) add(i,j);
//~ DBG(corners);
}
void getAffected(int a, vector<pair<int,int>> &affected){
int r = pos[a].r;
int c = pos[a].c;
forit(i,r-1,r) forit(j,c-1,c) affected.push_back({i,j});
}
int swap_seats(int a, int b) {
vector<pair<int,int>> affected;
getAffected(a, affected);
getAffected(b, affected);
assert(SZ(affected) == 8);
sort(ALL(affected));
affected.resize(unique(ALL(affected))-affected.begin());
for(const auto &x: affected) rem(x.first, x.second);
//~ DBG("remueve");
P &A = pos[a], &B = pos[b];
swap(seats[A.r][A.c], seats[B.r][B.c]);
swap(A,B);
for(const auto &x: affected) add(x.first, x.second);
//~ DBG("agrega");
//~ DBG(corners);
return corners.query(0,n);
}
#ifdef LOCAL
#include "grader.cpp"
#endif
