#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;
bool is;
vector<int> mnx, mxx, mny, mxy;
vector<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 n, int m, vector<int> r, vector<int> c) {
sz = n * 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.set(i, x[i]);
Y.set(i, y[i]);
}
}
int ans(int i, int j){
X.set(i, x[i]), Y.set(i, y[i]);
X.set(j, x[j]), Y.set(j, y[j]);
int last = 0, res = 0;
while(last < sz){
int mnx = X.getmin(0, last);
int mxx = X.getmax(0, last);
int mny = Y.getmin(0, last);
int mxy = Y.getmax(0, last);
int area = (mxx - mnx + 1) * (mxy - mny + 1);
if(area == last + 1){
last = area;
res++;
} else {
last = area - 1;
}
}
return res;
}
int swap_seats(int i, int j){
swap(x[i], x[j]);
swap(y[i], y[j]);
if(is){
return ans(i, j);
}
if(i > j) swap(i, 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;
}
