/*
_____________________.
|____________________| $$\ $$\ $$\ $$\
|____________________| $$ | \__| $$ | $$ |
|____________________| $$$$$$\ $$$$$$\ $$$$$$\ $$$$$$$\ $$$$$$$\ $$$$$$\ $$\ $$$$$$\ $$$$$$$\ $$$$$$\ $$$$$$$\
|____________________| \_$$ _| $$ __$$\ \____$$\ $$ __$$\ $$ _____| $$ __$$\ $$ |$$ __$$\ $$ __$$\\_$$ _| $$ _____|
|____________________| $$ | $$ | \__|$$$$$$$ |$$ | $$ |\$$$$$$\ $$ | \__|$$ |$$ / $$ |$$ | $$ | $$ | \$$$$$$\
$$ |$$\ $$ | $$ __$$ |$$ | $$ | \____$$\ $$ | $$ |$$ | $$ |$$ | $$ | $$ |$$\ \____$$\
\$$$$ |$$ | \$$$$$$$ |$$ | $$ |$$$$$$$ | $$ | $$ |\$$$$$$$ |$$ | $$ | \$$$$ |$$$$$$$ |
へ ♡ \____/ \__| \_______|\__| \__|\_______/ \__| \__| \____$$ |\__| \__| \____/ \_______/
૮ - ՛) $$\ $$ |
/ ⁻ ៸| \$$$$$$ | are human rights :3
乀 (ˍ,ل ل \______/
*/
//#include "candies_ioi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type,
less<pair<T, long long>>, rb_tree_tag,
tree_order_statistics_node_update>;
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf (ll)2e12+4
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)
#define fork(z) for(ll k=0;k<z;k++)
#define DEBUG
#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif
#include "seats.h"
std::vector<int> r;
struct node{
ll S,E,M,minval,maxval;
node *l,*r;
node(ll s,ll e){
S=s;E=e;minval=0;maxval=0;
M=(S+E)>>1;
if(S==E)return;
l=new node(S,M);
r=new node(M+1,E);
}
void up(ll p,ll v){
if(S==E){
minval=v;
maxval=v;
return;
}
if(p<=M)l->up(p,v);
else r->up(p,v);
minval=min(l->minval,r->minval);
maxval=max(l->maxval,r->maxval);
}
ll minqry(ll x,ll y){
if(x>E or y<S)return inf;
if(x<=S and E<=y){
return minval;
}
return min(l->minqry(x,y),r->minqry(x,y));
}
ll maxqry(ll x,ll y){
if(x>E or y<S)return -inf;
if(x<=S and E<=y){
return maxval;
}
return max(l->maxqry(x,y),r->maxqry(x,y));
}
};
const ll maxn=(ll)1e6+5;
node *x=new node(0,maxn), *y=new node(0,maxn);
ll posx[maxn],posy[maxn];
ll ans=0;
ll n;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
fori(H*W){
posx[i]=R[i];
posy[i]=C[i];
}
fori(H*W){
x->up(i,posx[i]);
y->up(i,posy[i]);
}
n=H*W;
fori(n){
//show2(i+1,(y->maxqry(0,i)-y->minqry(0,i)+1)*(1+x->maxqry(0,i)-x->minqry(0,i)))
ans+=(y->maxqry(0,i)-y->minqry(0,i)+1)*(1+x->maxqry(0,i)-x->minqry(0,i)) == i+1;
}
//show(ans)
}
int swap_seats(int a, int b) {
//a--;b--;
if(a==b){
return ans;
}
for(ll i=a;i<b;i++){
ans-=(y->maxqry(0,i)-y->minqry(0,i)+1)*(1+x->maxqry(0,i)-x->minqry(0,i)) == i+1;
}
x->up(a,posx[b]);
x->up(b,posx[a]);
y->up(a,posy[b]);
y->up(b,posy[a]);
swap(posx[a],posx[b]);
swap(posy[a],posy[b]);
for(ll i=a;i<b;i++){
ans+=(y->maxqry(0,i)-y->minqry(0,i)+1)*(1+x->maxqry(0,i)-x->minqry(0,i)) == i+1;
}
return ans;
}
