#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
const int N = 1e6 + 5;
const int inf = 1e9 + 7;
struct ST{
vector<int> Min, Max;
int N;
ST(int N): N(N){
Min.resize(N << 2);
Max.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx) { Min[x] = Max[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int getmax(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return Max[x];
int m = (lx + rx) >> 1;
return max(getmax(l, r, lx, m, x << 1), getmax(l, r, m + 1, rx, x << 1 | 1));
}
int getmax(int l, int r){
return getmax(l, r, 0, N, 1);
}
int getmin(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return inf;
if(lx >= l && rx <= r) return Min[x];
int m = (lx + rx) >> 1;
return min(getmin(l, r, lx, m, x << 1), getmin(l, r, m + 1, rx, x << 1 | 1));
}
int getmin(int l, int r){
return getmin(l, r, 0, N, 1);
}
};
//~ }X(N), Y(N);
int cnt, sz, n, m;
bool is;
vector<int> mnx_, mxx_, mny_, mxy_;
deque<ar<int, 2>> mnx, mxx, mny, mxy;
vector<int> x, y;
vector<set<int>> X, Y;
bool check(int i){
if((mxx_[i] - mnx_[i] + 1) * (mxy_[i] - mny_[i] + 1) == i + 1){
return true;
}
return false;
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
n = h, m = w;
sz = n * m;
X.resize(n), Y.resize(m);
mnx_.resize(sz);
mxx_.resize(sz);
mny_.resize(sz);
mxy_.resize(sz);
swap(x, r);
swap(y, c);
cnt = 0;
for(int i=0;i<sz;i++){
mnx_[i] = mxx_[i] = x[i];
mny_[i] = mxy_[i] = y[i];
if(i){
mnx_[i] = min(mnx_[i], mnx_[i - 1]);
mny_[i] = min(mny_[i], mny_[i - 1]);
mxx_[i] = max(mxx_[i], mxx_[i - 1]);
mxy_[i] = max(mxy_[i], mxy_[i - 1]);
}
if(check(i)) cnt++;
}
is = 0;
if(max(n, m) <= 1000){
is = 1;
for(int i=0;i<sz;i++){
X[x[i]].insert(i);
Y[y[i]].insert(i);
//~ X.set(i, x[i]);
//~ Y.set(i, y[i]);
}
for(int i=n-1;~i;i--){
int p = *X[i].begin();
if(mxx.empty() || p < mxx[0][0]) mxx.push_front({p, i});
while(!mnx.empty() && mnx.back()[0] > p) mnx.pop_back();
mnx.push_back({p, i});
}
for(int i=m-1;~i;i--){
int p = *Y[i].begin();
if(mxy.empty() || p < mxy[0][0]) mxy.push_front({p, i});
while(!mny.empty() && mny.back()[0] > p) mny.pop_back();
mny.push_back({p, i});
}
}
}
int ans(int i, int j){
X[x[i]].erase(i), Y[y[i]].erase(i);
X[x[j]].erase(j), Y[y[j]].erase(j);
swap(x[i], x[j]), swap(y[i], y[j]);
X[x[i]].insert(i), Y[y[i]].insert(i);
X[x[j]].insert(j), Y[y[j]].insert(j);
mxx.clear(), mnx.clear();
for(int i=n-1;~i;i--){
int p = *X[i].begin();
if(mxx.empty() || p < mxx[0][0]) mxx.push_front({p, i});
while(!mnx.empty() && mnx.back()[0] > p) mnx.pop_back();
mnx.push_back({p, i});
}
mxy.clear(), mny.clear();
for(int i=m-1;~i;i--){
int p = *Y[i].begin();
if(mxy.empty() || p < mxy[0][0]) mxy.push_front({p, i});
while(!mny.empty() && mny.back()[0] > p) mny.pop_back();
mny.push_back({p, i});
}
//~ for(auto x : mxx) cout<<x[0]<<" ";
//~ cout<<"\n";
//~ for(auto x : mnx) cout<<x[0]<<" ";
//~ cout<<"\n";
//~ for(auto x : mxy) cout<<x[0]<<" ";
//~ cout<<"\n";
//~ for(auto x : mny) cout<<x[0]<<" ";
//~ cout<<"\n";
//~ cout<<"here"<<endl;
int last = 1, res = 1, cnt = 0;
while(last < sz){
int mnx_ = (*--lower_bound(mnx.begin(), mnx.end(), (ar<int, 2>){last + 1, 0}))[1];
int mxx_ = (*--lower_bound(mxx.begin(), mxx.end(), (ar<int, 2>){last + 1, 0}))[1];
int mny_ = (*--lower_bound(mny.begin(), mny.end(), (ar<int, 2>){last + 1, 0}))[1];
int mxy_ = (*--lower_bound(mxy.begin(), mxy.end(), (ar<int, 2>){last + 1, 0}))[1];
int area = (mxx_ - mnx_ + 1) * (mxy_ - mny_ + 1);
if(area == last + 1){
last++;
res++;
} else {
last = area - 1;
}
cnt++;
}
return res;
}
int swap_seats(int i, int j){
if(i > j) swap(i, j);
if(is){
return ans(i, j);
}
swap(x[i], x[j]);
swap(y[i], y[j]);
for(int k=i;k<=j;k++){
if(check(k)) cnt--;
mnx_[k] = mxx_[k] = x[k];
mny_[k] = mxy_[k] = y[k];
if(k){
mnx_[k] = min(mnx_[k], mnx_[k - 1]);
mny_[k] = min(mny_[k], mny_[k - 1]);
mxx_[k] = max(mxx_[k], mxx_[k - 1]);
mxy_[k] = max(mxy_[k], mxy_[k - 1]);
}
if(check(k)) cnt++;
}
return cnt;
}
