#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> seg[4000005];
vector<vector<int> > rect;
int lazy[4000005], n, m;
vector<int> a, b;
pair<int, int> combine(pair<int, int> x, pair<int, int> y)
{
if (x.first<y.first)
return x;
if (x.first>y.first)
return y;
return {x.first, x.second+y.second};
}
void push(int i, int l, int r)
{
if (l<r)
{
seg[i*2].first+=lazy[i];
seg[i*2+1].first+=lazy[i];
lazy[i*2]+=lazy[i];
lazy[i*2+1]+=lazy[i];
}
lazy[i]=0;
}
void build(int i, int l, int r)
{
if (l==r)
{
seg[i]={0, 1};
return;
}
int mid=(l+r)/2;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
seg[i]=combine(seg[i*2], seg[i*2+1]);
}
void upd(int i, int l, int r, int ql, int qr, int val)
{
if (ql<=l && r<=qr)
{
seg[i].first+=val;
lazy[i]+=val;
return;
}
push(i, l, r);
int mid=(l+r)/2;
if (l<=qr && ql<=mid)
upd(i*2, l, mid, ql, qr, val);
if (mid<qr && ql<=r)
upd(i*2+1, mid+1, r, ql, qr, val);
seg[i]=combine(seg[i*2], seg[i*2+1]);
}
pair<int, int> qry(int i, int l, int r, int ql, int qr)
{
if (ql<=l && r<=qr)
return seg[i];
push(i, l, r);
int mid=(l+r)/2;
pair<int, int> res={1e9, 1};
if (l<=qr && ql<=mid)
res=combine(res, qry(i*2, l, mid, ql, qr));
if (mid<qr && ql<=r)
res=combine(res, qry(i*2+1, mid+1, r, ql, qr));
return res;
}
void update(int x, int y, int val)
{
//cout << "update " << x << ' ' << y << ' ' << "val: ";
vector<int> tmp;
tmp.push_back(x==0?n*m:(y==0?n*m:rect[x-1][y-1]));
tmp.push_back(x==0?n*m:(y==m?n*m:rect[x-1][y]));
tmp.push_back(x==n?n*m:(y==0?n*m:rect[x][y-1]));
tmp.push_back(x==n?n*m:(y==m?n*m:rect[x][y]));
sort(tmp.begin(), tmp.end());
//cout << tmp[0] << ' ' << tmp[1] << ' ' << tmp[2] << ' ' << tmp[3] << '\n';
if (tmp[0]<tmp[1])
upd(1, 0, n*m, tmp[0], tmp[1]-1, val);
if (tmp[2]<tmp[3])
upd(1, 0, n*m, tmp[2], tmp[3]-1, val);
}
void give_initial_chart(int N, int M, vector<int> A, vector<int> B)
{
n=N, m=M, a=A, b=B;
for (int i=0; i<n; i++)
{
vector<int> tmp(m);
rect.push_back(tmp);
}
for (int i=0; i<n*m; i++)
rect[a[i]][b[i]]=i;
build(1, 0, n*m);
for (int i=0; i<=n; i++)
for (int j=0; j<=m; j++)
update(i, j, 1);
//for (int i=0; i<=n*m; i++)
// cout << qry(1, 0, n*m, i, i).first << ' ';
//cout << '\n';
}
int swap_seats(int x, int y)
{
int xa=a[x], xb=b[x], ya=a[y], yb=b[y];
vector<pair<int, int> > tmp;
tmp.push_back({xa, xb});
tmp.push_back({xa, xb+1});
tmp.push_back({xa+1, xb});
tmp.push_back({xa+1, xb+1});
tmp.push_back({ya, yb});
tmp.push_back({ya, yb+1});
tmp.push_back({ya+1, yb});
tmp.push_back({ya+1, yb+1});
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end())-tmp.begin());
for (pair<int, int> p:tmp)
update(p.first, p.second, -1);
//for (int i=0; i<=n*m; i++)
// cout << qry(1, 0, n*m, i, i).first << ' ';
//cout << '\n';
rect[xa][xb]=y;
rect[ya][yb]=x;
for (pair<int, int> p:tmp)
update(p.first, p.second, 1);
a[x]=ya, b[x]=yb, a[y]=xa, b[y]=xb;
//for (int i=0; i<=n*m; i++)
// cout << qry(1, 0, n*m, i, i).first << ' ';
//cout << '\n';
return qry(1, 0, n*m, 0, n*m-1).second;
}
