#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
int l1,r1;
int l2,r2;
node(){
l1 = 1e9,r1 = 0;
l2 = 1e9,r2 = 0;
}
node(int a,int b,int c,int d){
l1 = a,r1 = b;
l2 = c,r2 = d;
}
int size(){
return (r1 - l1 + 1) * (r2 - l2 + 1);
}
};
node merge(node a,node b){
node ret;
ret.l1 = min(a.l1,b.l1);
ret.r1 = max(a.r1,b.r1);
ret.l2 = min(a.l2,b.l2);
ret.r2 = max(a.r2,b.r2);
return ret;
}
struct SegTree{
vector<node> t;
int n;
SegTree(int size){
n = size;
t.assign(4*n,node());
}
void upd(int v,int tl,int tr,int pos,node val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd(v*2,tl,tm,pos,val);
}
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return node();
if(l <= tl && tr <= r)
return t[v];
int tm = (tl + tr)/2;
return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int pos,node val){
upd(1,0,n-1,pos,val);
}
node get(int l,int r){
return get(1,0,n-1,l,r);
}
node get(int x){
return get(0,x);
}
};
node v[N];
int cnt = 0;
vector<int> r,c;
SegTree tree(N);
void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
r = R;
c = C;
for(int i = 0;i<h*w;i++){
v[i] = node(r[i],r[i],c[i],c[i]);
tree.upd(i,v[i]);
if(tree.get(i).size() == i+1)
cnt++;
}
}
int swap_seats(int a, int b) {
if(a > b)swap(a,b);
for(int i = a;i<=b;i++){
if(tree.get(i).size() == i+1)
cnt--;
}
swap(v[a],v[b]);
tree.upd(a,v[a]);
tree.upd(b,v[b]);
for(int i = a;i<=b;i++){
if(tree.get(i).size() == i+1)
cnt++;
}
return cnt;
}
