#include "seats.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 1 << 20;
const int INF = 1e9;
int n, m;
struct SegmentTree
{
struct Node
{
std::pair <int,int> min;
std::pair <int,int> lazy;
int cnt;
Node()
{
min = lazy = {0, 0};
cnt = 0;
}
friend Node operator + (const Node &left, const Node &right)
{
Node res;
res.min = std::min(left.min, right.min);
if (res.min == left.min) res.cnt += left.cnt;
if (res.min == right.min) res.cnt += right.cnt;
return res;
}
};
Node tree[2*MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].min = {0, 0};
tree[node].cnt = 1;
return;
}
int mid = l + r >> 1;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = tree[2*node] + tree[2*node + 1];
}
void push(int node, int l, int r)
{
if (tree[node].lazy == std::make_pair(0, 0))
{
return;
}
tree[node].min.first += tree[node].lazy.first;
tree[node].min.second += tree[node].lazy.second;
if (l < r)
{
tree[2*node].lazy.first += tree[node].lazy.first;
tree[2*node].lazy.second += tree[node].lazy.second;
tree[2*node + 1].lazy.first += tree[node].lazy.first;
tree[2*node + 1].lazy.second += tree[node].lazy.second;
}
tree[node].lazy = {0, 0};
}
void update(int l, int r, int node, int queryL, int queryR, std::pair <int,int> queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy = queryVal;
push(node, l, r);
return;
}
int mid = l + r >> 1;
update(l, mid, 2*node, queryL, queryR, queryVal);
update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
tree[node] = tree[2*node] + tree[2*node + 1];
}
void build()
{
build(1, n * m, 1);
}
void update(int l, int r, int val, int val2)
{
if (l > r) return;
update(1, n * m, 1, l, r, {val, val2});
}
int query()
{
return tree[1].cnt;
}
};
SegmentTree tree;
std::vector <int> t[MAXN];
std::vector <int> r, c;
std::set <std::pair <int,int>> used;
void addL(int row, int col)
{
if (used.count({row, col}))
{
return;
}
used.insert({row, col});
std::vector <int> vals;
vals.push_back(t[row][col]);
vals.push_back(t[row - 1][col]);
vals.push_back(t[row][col - 1]);
vals.push_back(t[row - 1][col - 1]);
std::sort(vals.begin(), vals.end());
tree.update(vals[0], vals[1] - 1, 1, 0);
tree.update(vals[2], vals[3] - 1, 0, 1);
}
void remL(int row, int col)
{
// std::cout << "remL: " << row << ' ' << col << '\n' << std::flush;
if (used.count({row, col}))
{
return;
}
used.insert({row, col});
std::vector <int> vals;
vals.push_back(t[row][col]);
vals.push_back(t[row - 1][col]);
vals.push_back(t[row][col - 1]);
vals.push_back(t[row - 1][col - 1]);
std::sort(vals.begin(), vals.end());
tree.update(vals[0], vals[1] - 1, -1, 0);
tree.update(vals[2], vals[3] - 1, 0, -1);
}
void add(int row, int col)
{
addL(row, col);
addL(row + 1, col);
addL(row, col + 1);
addL(row + 1, col + 1);
}
void rem(int row, int col)
{
remL(row, col);
remL(row + 1, col);
remL(row, col + 1);
remL(row + 1, col + 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
n = H;
m = W;
for (int i = 0 ; i <= n + 1 ; ++i)
{
t[i].resize(m + 2, n * m + 1);
}
C.insert(C.begin(), -1);
R.insert(R.begin(), -1);
for (int &val : R) val++;
for (int &val : C) val++;
r = R; c = C;
for (int i = 1 ; i <= n * m ; ++i)
{
t[R[i]][C[i]] = i;
}
tree.build();
for (int i = 1 ; i <= n + 1 ; ++i)
{
for (int j = 1 ; j <= m + 1 ; ++j)
{
addL(i, j);
}
}
tree.query();
}
int swap_seats(int a, int b)
{
a++; b++;
int rowA = r[a];
int colA = c[a];
int rowB = r[b];
int colB = c[b];
used.clear();
rem(rowA, colA);
rem(rowB, colB);
std::swap(t[rowA][colA], t[rowB][colB]);
std::swap(c[a], c[b]);
std::swap(r[a], r[b]);
used.clear();
add(rowA, colA);
add(rowB, colB);
return tree.query();
}
