#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
const int C = 6;
int seg[4*N][C];
int tmp[C];
int lz1[4*N],lz2[4*N];
int sz;
int n,m;
void pull(int node){
for(int i = 0;i < C;i++){
seg[node][i] = 0;
}
///apply update
for(int j = 0;j < 2;j++){
if(!lz2[node*2 + j]){
for(int i = 0;i < C;i++){
seg[node][min(i + lz1[node*2 + j],5)]+=seg[node*2 + j][i];
}
}
}
}
void upd(int ql, int qr, int tip, int nr, int l = 0, int r = sz - 1, int node = 1){
if(r < ql || qr < l)return;
if(ql <= l && r <= qr){
if(tip == 0){
lz1[node]+=nr;
}else{
lz2[node]+=nr;
}
}else{
int mij = (l + r)/2;
upd(ql, qr, tip, nr, l, mij, node*2);
upd(ql, qr, tip, nr, mij + 1, r, node*2 + 1);
pull(node);
}
}
void build(int l = 0, int r = sz - 1, int node = 1){
if(l != r){
int mij = (l + r)/2;
build(l, mij, node*2);
build(mij + 1, r, node*2 + 1);
pull(node);
}else{
seg[node][0] = 1;
}
}
void dbg(int l = 0, int r = sz - 1, int node = 1){
if(l != r){
int mij = (l + r)/2;
dbg(l, mij, node*2);
dbg(mij + 1, r, node*2 + 1);
}
cout<<"debug"<<l<<' '<<r<<' '<<node<<' '<<lz1[node]<<' '<<lz2[node]<<' ';
for(int i = 0;i < 6;i++){
cout<<seg[node][i]<<' ';
}
cout<<'\n';
}
int query(){
for(int i = 0;i < C;i++){
tmp[i] = 0;
}
///apply update
if(!lz2[1]){
for(int i = 0;i < C;i++){
tmp[min(i + lz1[1],5)]+=seg[1][i];
}
}
return tmp[4];
}
vector<vector<int>> v;
vector <int> x,y;
vector <int> tf;
void add2(int x, int y){
if(x < 0 || y < 0 || x >= n || y >= m){
tf.push_back(sz);
}else{
tf.push_back(v[x][y]);
}
}
void add(int x, int y, int t){
tf.clear();
for(int i = x;i < x + 2;i++){
for(int j = y;j < y + 2;j++){
add2(i, j);
}
}
sort(tf.begin(),tf.end());
upd(tf[0], tf[1] - 1, 0, t);
upd(tf[2], tf[3] - 1, 1, t);
}
void give_initial_chart(int n2, int m2, std::vector<int> a, std::vector<int> b) {
n = n2;m = m2;
v.assign(n, vector<int>(m,0));
x = a;y = b;
sz = n*m;
for(int i = 0;i < n*m;i++){
v[x[i]][y[i]] = i;
}
build();
for(int i = -1;i < n;i++){
for(int j = -1;j < m;j++){
add(i, j, 1);
}
}
//cout<<query()<<'\n';
//dbg();
}
int prevans = -1;
int swap_seats(int a, int b){
if(a > b)swap(a,b);
swap(x[a],x[b]);
swap(y[a],y[b]);
swap(v[x[a]][y[a]],v[x[b]][y[b]]);
///add update
for(int i = x[a] - 1;i < x[a] + 1;i++){
for(int j = y[a] - 1;j < y[a] + 1;j++){
add(i, j, 1);
}
}
for(int i = x[b] - 1;i < x[b] + 1;i++){
for(int j = y[b] - 1;j < y[b] + 1;j++){
add(i, j, 1);
}
}
swap(v[x[a]][y[a]],v[x[b]][y[b]]);
///remove old update
for(int i = x[a] - 1;i < x[a] + 1;i++){
for(int j = y[a] - 1;j < y[a] + 1;j++){
add(i, j, -1);
}
}
for(int i = x[b] - 1;i < x[b] + 1;i++){
for(int j = y[b] - 1;j < y[b] + 1;j++){
add(i, j, -1);
}
}
swap(v[x[a]][y[a]],v[x[b]][y[b]]);
return query();
}
/**
1 1 1
0 0
0 0
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
**/
