#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int minV[1<<21], minC[1<<21], lazy[1<<21];
void propagate(int i, int l, int r){
minV[i] += lazy[i];
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void merge(int i){
if(minV[i*2] == minV[i*2+1]) minV[i] = minV[i*2], minC[i] = minC[i*2] + minC[i*2+1];
else if(minV[i*2] < minV[i*2+1]) minV[i] = minV[i*2], minC[i] = minC[i*2];
else minV[i] = minV[i*2+1], minC[i] = minC[i*2+1];
}
void init(int i, int l, int r, int *A){
lazy[i] = 0;
if(l==r){
minV[i] = A[l], minC[i] = 1;
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
merge(i);
}
void update(int i, int l, int r, int s, int e, int v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
merge(i);
}
pair<int, int> query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return make_pair(1e9, 0);
if(s<=l && r<=e) return make_pair(minV[i], minC[i]);
int m = (l+r)>>1;
pair<int, int> p1 = query(i*2, l, m, s, e);
pair<int, int> p2 = query(i*2+1, m+1, r, s, e);
if(p1.first == p2.first) return make_pair(p1.first, p1.second + p2.second);
else if(p1.first < p2.first) return p1;
else return p2;
}
} tree;
int n, m;
vector<vector<int> > arr;
int R[1000002], C[1000002];
vector<vector<int> > st, en;
vector<vector<int> > st2, en2;
int sumArray[1000002];
void update(int X, int Y, bool first=0){
if(!first){
tree.update(1, 0, n*m-1, st[X][Y], en[X][Y]-1, -1);
tree.update(1, 0, n*m-1, st2[X][Y], en2[X][Y]-1, -5);
}
vector<int> v;
for(int ti=X-1; ti<=X; ti++){
for(int tj=Y-1; tj<=Y; tj++){
if(ti<0||ti>=n||tj<0||tj>=m) continue;
v.push_back(arr[ti][tj]);
}
}
sort(v.begin(), v.end());
st[X][Y] = v[0];
en[X][Y] = ((int)v.size() <= 1) ? n*m : v[1];
st2[X][Y] = ((int)v.size() <= 2) ? n*m : v[2];
en2[X][Y] = ((int)v.size() <= 2) ? n*m : v[3];
if(!first){
tree.update(1, 0, n*m-1, st[X][Y], en[X][Y]-1, 1);
tree.update(1, 0, n*m-1, st2[X][Y], en2[X][Y]-1, 5);
}
else{
sumArray[st[X][Y]]++;
sumArray[en[X][Y]]--;
sumArray[st2[X][Y]]+=5;
sumArray[en2[X][Y]]-=5;
}
}
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C){
n = H, m = W;
arr.resize(n);
for(int i=0; i<n; i++) arr[i].resize(m);
for(int i=0; i<n*m; i++){
R[i] = _R[i], C[i] = _C[i];
arr[R[i]][C[i]] = i;
}
st.resize(n+1), en.resize(n+1);
st2.resize(n+1), en2.resize(n+1);
for(int i=0; i<=n; i++){
st[i].resize(m+1);
st2[i].resize(m+1);
en[i].resize(m+1);
en2[i].resize(m+1);
for(int j=0; j<=m; j++){
update(i, j, 1);
}
}
for(int i=1; i<=n*m; i++) sumArray[i] += sumArray[i-1];
tree.init(1, 0, n*m-1, sumArray);
}
int swap_seats(int a, int b){
swap(arr[R[a]][C[a]], arr[R[b]][C[b]]);
swap(R[a], R[b]);
swap(C[a], C[b]);
for(int x=R[a]; x<=R[a]+1; x++) for(int y=C[a]; y<=C[a]+1; y++) update(x, y);
for(int x=R[b]; x<=R[b]+1; x++) for(int y=C[b]; y<=C[b]+1; y++) update(x, y);
pair<int, int> p = tree.query(1, 0, n*m-1, 0, n*m-1);
assert(p.first == 4);
return p.second;
}
