#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e6 + 20;
const int dx[] = {-1 , -1 , 1 , 1 , 0 , 0 , 1 ,-1};
const int dy[] = {-1 , 1 ,-1 , 1 , 1 ,-1 , 0 , 0};
int n , m , all , x[maxn] , y[maxn];
set<int> stx[maxn] , sty[maxn];
vector<int> pos[maxn] , has[maxn];
int mn[maxn * 4] , cnt[maxn * 4] , Add[maxn * 4];
void build(int s = 0 , int e = all , int v = 1)
{
cnt[v] = e - s;
if(e - s < 2)
return;
int m = (s + e) / 2;
build(s , m , 2 * v);
build(m , e , 2 * v + 1);
}
void add(int l , int r , int val , int s = 0 , int e = all , int v = 1)
{
while(r != all);
if(l <= s && e <= r)
{
Add[v] += val;
mn[v] += val;
return;
}
if(r <= s || e <= l)
return;
int m = (s + e) / 2;
add(l , r , val , s , m , 2 * v);
add(l , r , val , m , e , 2 * v + 1);
mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
cnt[v] = 0;
if(mn[v] == mn[2 * v])
cnt[v] += cnt[2 * v];
if(mn[v] == mn[2 * v + 1])
cnt[v] += cnt[2 * v + 1];
mn[v] += Add[v];
}
void d(int x , int y , int val)
{
if(x <= 0 || x > n || y <= 0 || y > m)
return;
if(val == -1 && !has[x][y])
return;
if(val == 1 && has[x][y])
return;
has[x][y] ^= 1;
val *= -1;
for(int i = 0; i < 8; i++)
{
int nx = x + dx[i] , ny = y + dy[i];
if(i == 4)
val *= -1;
add(pos[x][y] , all , pos[nx][ny] < pos[x][y]? -val : val);
}
}
void addR(int i)
{
if(!stx[x[i]].empty())
add(*stx[x[i]].begin() , all , -2);
stx[x[i]].insert(i);
add(*stx[x[i]].begin() , all , 2);
}
void addC(int i)
{
if(!sty[y[i]].empty())
add(*sty[y[i]].begin() , all , -2);
sty[y[i]].insert(i);
add(*sty[y[i]].begin() , all , 2);
}
void remR(int i)
{
add(*stx[x[i]].begin() , all , -2);
stx[x[i]].erase(i);
if(!stx[x[i]].empty())
add(*stx[x[i]].begin() , all , 2);
}
void remC(int i)
{
add(*sty[y[i]].begin() , all , -2);
sty[y[i]].erase(i);
if(!sty[y[i]].empty())
add(*sty[y[i]].begin() , all , 2);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H , m = W;
all = n * m;
build();
for(int i = 0; i <= n + 1; i++)
for(int j = 0; j <= m + 1; j++)
pos[i].pb(1e9) , has[i].pb(0);
for(int i = 0; i < all; i++)
{
x[i] = R[i] + 1;
y[i] = C[i] + 1;
pos[x[i]][y[i]] = i;
}
for(int i = 0; i < all; i++)
{
addC(i) , addR(i);
d(x[i] , y[i] , 1);
}
}
int swap_seats(int a, int b)
{
remR(a) , remR(b);
remC(a) , remC(b);
d(x[a] , y[a] , -1) , d(x[b] , y[b] , -1);
for(int i = 0; i < 8; i++)
{
d(x[a] + dx[i] , y[a] + dy[i] , -1);
d(x[b] + dx[i] , y[b] + dy[i] , -1);
}
swap(x[a] , x[b]) , swap(y[a] , y[b]);
swap(pos[x[a]][y[a]] , pos[x[b]][y[b]]);
addR(a) , addR(b);
addC(a) , addC(b);
d(x[a] , y[a] , 1) , d(x[b] , y[b] , 1);
for(int i = 0; i < 8; i++)
{
d(x[a] + dx[i] , y[a] + dy[i] , 1);
d(x[b] + dx[i] , y[b] + dy[i] , 1);
}
return cnt[1];
}
