#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using vi = vector<int>;
const int MX = (int)1e6+10;
vi r, c;
int n, m, ans;
int a[MX];
int rMin[MX*2], rMax[MX*2], cMin[MX*2], cMax[MX*2];
void upd(int x, int v, int seg[], bool t, int p=0, int l=0, int r=n*m){
if(l==r){ seg[p] = v; return; }
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
if(x<=mid) upd(x,v,seg,t,p+1,l,mid);
else upd(x,v,seg,t,rp,mid+1,r);
if(t) seg[p] = max(seg[p+1],seg[rp]);
else seg[p] = min(seg[p+1],seg[rp]);
}
int rmq(int i, int j, int seg[], bool t, int p=0, int l=0, int r=n*m){
if(i>r or j<l or i>j) return t?0:MX;
if(i<=l and r<=j) return seg[p];
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
int le = t?0:MX; int ri = le;
if(i<=mid) le = rmq(i,j,seg,t,p+1,l,mid);
if(j>mid) ri = rmq(i,j,seg,t,rp,mid+1,r);
if(t) return max(le,ri);
return min(le,ri);
}
void give_initial_chart(int H, int W, vi R, vi C) {
n = H, m = W; r = R; c = C;
fill(rMin,rMin+MX*2,n*m);
fill(cMin,cMin+MX*2,n*m);
for(int i = 0; i < n*m; i++){
upd(i,r[i],rMin,0); upd(i,r[i],rMax,1); upd(i,c[i],cMin,0); upd(i,c[i],cMax,1);
a[i] = ((i+1)==((rmq(0,i,rMax,1)-rmq(0,i,rMin,0)+1)*((rmq(0,i,cMax,1)-rmq(0,i,cMin,0)+1))));
ans+=a[i];
}
}
int swap_seats(int x, int y) {
if(x>y) swap(x,y);
swap(r[x],r[y]); swap(c[x],c[y]);
for(int i = x; i <= y; i++){
ans-=a[i];
if(i==x or i==y){
upd(i,r[i],rMin,0); upd(i,r[i],rMax,1); upd(i,c[i],cMin,0); upd(i,c[i],cMax,1);
}
a[i] = ((i+1)==((rmq(0,i,rMax,1)-rmq(0,i,rMin,0)+1)*((rmq(0,i,cMax,1)-rmq(0,i,cMin,0)+1))));
ans+=a[i];
}
return ans;
}
