#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e6 + 5;
const int inf = 1e9;
typedef long long ll;
typedef pair<int,int> Pair;
ll mars[Nmax];
int N, M, P;
int posL[Nmax], posC[Nmax];
vector< vector<int> > matrix;
vector< vector< pair<Pair, Pair> > > coef;
///////////////////////////////////////////////////
struct info
{
ll mn; int cnt;
};
info operator + (info a, info b)
{
if(a.mn < b.mn) return a;
if(b.mn < a.mn) return b;
return {a.mn, a.cnt + b.cnt};
}
void operator += (info &a, ll b)
{
a.mn += b;
}
//////////////////////////////////////////////////
#define mid ((st+dr)>>1)
#define left_son ((node<<1))
#define right_son ((node<<1)|1)
class SegTree
{
info a[Nmax<<2];
ll lazy[Nmax<<2];
void propag(int node)
{
if(!lazy[node]) return;
lazy[left_son] += lazy[node];
lazy[right_son] += lazy[node];
a[left_son] += lazy[node];
a[right_son] += lazy[node];
lazy[node] = 0;
}
public:
void build(int node, int st, int dr, ll A[])
{
lazy[node] = 0;
if(st == dr)
{
a[node] = {A[st], 1};
return;
}
build(left_son, st, mid, A);
build(right_son, mid+1, dr, A);
a[node] = a[left_son] + a[right_son];
}
void update(int node, int st, int dr, int L, int R, int add)
{
if(L > R) return;
if(L <= st && dr <= R)
{
lazy[node] += add;
a[node] += add;
return;
}
propag(node);
if(L <= mid) update(left_son, st, mid, L, R, add);
if(mid < R) update(right_son, mid+1, dr, L, R, add);
a[node] = a[left_son] + a[right_son];
}
info query()
{
return a[1];
}
} aint;
pair<Pair, Pair> get_coef(int x, int y)
{
vector<int> aux;
aux.push_back(matrix[x][y]);
aux.push_back(matrix[x+1][y]);
aux.push_back(matrix[x][y+1]);
aux.push_back(matrix[x+1][y+1]);
sort(aux.begin(), aux.end());
return { {aux[0], aux[1] - 1}, {aux[2], aux[3] - 1} };
}
void add_mars(Pair a, int c)
{
mars[a.first] += c; mars[a.second+1] -= c;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
N = H; M = W; P = N * M;
int i, j;
matrix.resize(N+2);
for(auto &it : matrix) it.resize(M+2, 0);
coef.resize(N+1);
for(auto &it : coef) it.resize(M+1);
for(i=0; i<=N+1; ++i)
for(j=0; j<=M+1; ++j)
matrix[i][j] = ( (1 <= i && i <= N && 1 <= j && j <= M) ? 0 : P);
for(i=0; i<P; ++i)
{
++R[i]; ++C[i];
posL[i] = R[i], posC[i] = C[i];
matrix[R[i]][C[i]] = i;
}
for(i=0; i<=N; ++i)
for(j=0; j<=M; ++j) /// ce coeficient are patratul cu coltul stanga-sus in (i,j) ?
coef[i][j] = get_coef(i, j);
for(i=0; i<=P; ++i) mars[i] = 0;
for(i=0; i<=N; ++i)
for(j=0; j<=M; ++j)
{
add_mars(coef[i][j].first, 1);
add_mars(coef[i][j].second, inf);
}
for(i=1; i<P; ++i)
mars[i] += mars[i-1];
aint.build(1, 0, P-1, mars);
}
int swap_seats(int id1, int id2)
{
int l1, c1, l2, c2;
l1 = posL[id1]; c1 = posC[id1];
l2 = posL[id2]; c2 = posC[id2];
vector<Pair> changes;
changes.push_back({l1, c1});
changes.push_back({l1-1, c1});
changes.push_back({l1, c1-1});
changes.push_back({l1-1, c1-1});
changes.push_back({l2, c2});
changes.push_back({l2-1, c2});
changes.push_back({l2, c2-1});
changes.push_back({l2-1, c2-1});
sort(changes.begin(), changes.end());
changes.erase( unique(changes.begin(), changes.end()), changes.end() );
swap(posL[id1], posL[id2]);
swap(posC[id1], posC[id2]);
swap(matrix[l1][c1], matrix[l2][c2]);
for(auto it : changes)
{
int pc, pl;
tie(pl, pc) = it;
auto C = coef[pl][pc];
aint.update(1, 0, P-1, C.first.first, C.first.second, -1);
aint.update(1, 0, P-1, C.second.first, C.second.second, -inf);
C = coef[pl][pc] = get_coef(pl, pc);
aint.update(1, 0, P-1, C.first.first, C.first.second, +1);
aint.update(1, 0, P-1, C.second.first, C.second.second, +inf);
}
auto res = aint.query();
assert(res.mn == 4);
return res.cnt;
}
