#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> x, y, xmn, ymn, xmx, ymx;
set<int> xs[1005], ys[1005];
int n, m, sum;
void give_initial_chart(int N, int M, vector<int> X, vector<int> Y)
{
n=N;
m=M;
x=X;
y=Y;
if (n<=1000 && m<=1000)
{
for (int i=0; i<n*m; i++)
{
xs[x[i]].insert(i);
ys[y[i]].insert(i);
}
}
else
{
for (int i=0; i<n*m; i++)
{
if (!i)
{
xmn.push_back(x[i]);
ymn.push_back(y[i]);
xmx.push_back(x[i]);
ymx.push_back(y[i]);
}
else
{
xmn.push_back(min(xmn[i-1], x[i]));
ymn.push_back(min(ymn[i-1], y[i]));
xmx.push_back(max(xmx[i-1], x[i]));
ymx.push_back(max(ymx[i-1], y[i]));
}
sum+=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
}
}
}
int swap_seats(int a, int b)
{
if (a>b)
swap(a, b);
if (n<=1000 && m<=1000)
{
xs[x[a]].erase(a);
ys[y[a]].erase(a);
xs[x[b]].erase(b);
ys[y[b]].erase(b);
swap(x[a], x[b]);
swap(y[a], y[b]);
xs[x[a]].insert(a);
ys[y[a]].insert(a);
xs[x[b]].insert(b);
ys[y[b]].insert(b);
vector<pair<int, pair<int, int> > > v;
for (int i=0; i<n; i++)
v.push_back({*xs[i].begin(), {0, i}});
for (int i=0; i<m; i++)
v.push_back({*ys[i].begin(), {1, i}});
sort(v.begin(), v.end());
int Xmn=1e9, Xmx=-1, Ymn=1e9, Ymx=-1, ans=1;
for (int i=0; i<v.size(); i++)
{
if (v[i].first==v[i+1].first)
{
Xmn=min(Xmn, v[i].second.second);
Xmx=max(Xmx, v[i].second.second);
i++;
Ymn=min(Ymn, v[i].second.second);
Ymx=max(Ymx, v[i].second.second);
}
else if (v[i].second.first)
{
Ymn=min(Ymn, v[i].second.second);
Ymx=max(Ymx, v[i].second.second);
}
else
{
Xmn=min(Xmn, v[i].second.second);
Xmx=max(Xmx, v[i].second.second);
}
if (i+2<=v.size() && (Xmx-Xmn+1)*(Ymx-Ymn+1)<=v[i+1].first)
ans++;
}
return ans;
}
else
{
for (int i=a; i<b; i++)
sum-=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
swap(x[a], x[b]);
swap(y[a], y[b]);
for (int i=a; i<b; i++)
{
if (!i)
{
xmn[i]=x[i];
ymn[i]=y[i];
xmx[i]=x[i];
ymx[i]=y[i];
}
else
{
xmn[i]=min(xmn[i-1], x[i]);
ymn[i]=min(ymn[i-1], y[i]);
xmx[i]=max(xmx[i-1], x[i]);
ymx[i]=max(ymx[i-1], y[i]);
}
sum+=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
}
return sum;
}
}
