#include "seats.h"
#include <bits/stdc++.h>
#define a first
#define b second
#define mk make_pair
#define pb push_back
using namespace std;
const int N = (1e6 + 5);
const int inf = (1e9 + 7);
int n,m;
int r[N],c[N],ans = 0;
pair<pair<int,int>,pair<int,int> > t[N * 4],cur,er;
void build (int v = 1,int tl = 1,int tr = n * m) {
if (tl == tr) {
t[v].a.a = r[tl];
t[v].a.b = r[tl];
t[v].b.a = c[tl];
t[v].b.b = c[tl];
}
else {
int tm = (tl + tr) >> 1;
build (v + v,tl,tm);
build (v + v + 1,tm + 1,tr);
t[v].a.a = max(t[v + v].a.a,t[v + v + 1].a.a);
t[v].a.b = min(t[v + v].a.b,t[v + v + 1].a.b);
t[v].b.a = max(t[v + v].b.a,t[v + v + 1].b.a);
t[v].b.b = min(t[v + v].b.b,t[v + v + 1].b.b);
}
}
void update (int pos,int ca,int cb,int v = 1,int tl = 1,int tr = n * m) {
if (tl == tr) {
t[v].a.a = ca;
t[v].a.b = ca;
t[v].b.a = cb;
t[v].b.b = cb;
}
else {
int tm = (tl + tr) >> 1;
if (pos <= tm) update (pos,ca,cb,v + v,tl,tm);
else update (pos,ca,cb,v + v + 1,tm + 1,tr);
t[v].a.a = max(t[v + v].a.a,t[v + v + 1].a.a);
t[v].a.b = min(t[v + v].a.b,t[v + v + 1].a.b);
t[v].b.a = max(t[v + v].b.a,t[v + v + 1].b.a);
t[v].b.b = min(t[v + v].b.b,t[v + v + 1].b.b);
}
}
pair<pair<int,int>,pair<int,int> > get(int l,int r,int v = 1,int tl = 1,int tr = n * m) {
if (l > tr || r < tl) return er;
if (l <= tl && tr <= r)
return t[v];
int tm = (tl + tr) >> 1;
pair<pair<int,int>,pair<int,int> > c,d,e;
d = get(l,r,v + v,tl,tm);
e = get(l,r,v + v + 1,tm + 1,tr);
c.a.a = max(d.a.a,e.a.a);
c.a.b = min(d.a.b,e.a.b);
c.b.a = max(d.b.a,e.b.a);
c.b.b = min(d.b.b,e.b.b);
return c;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H,m = W;
for (int i = 0; i < R.size(); i ++)
r[i + 1] = R[i],c[i + 1] = C[i];
build();
}
int swap_seats(int a, int b) {
a ++,b ++;
update(a,r[b],c[b]);
update(b,r[a],c[a]);
int cr = r[a],cc = c[a];
r[a] = r[b],c[a] = c[b];
r[b] = cr,c[b] = cc;
er = {{-inf,inf},{-inf,inf}};
int i = 1,cnt = 0;
ans = 0;
while (i <= n * m) {
cur = get(1,i);
int rs = (cur.a.a - cur.a.b + 1) * (cur.b.a - cur.b.b + 1);
if (rs == i) ans ++;
i = max(rs,i + 1);
if (2010 < cnt) return ans;
cnt ++;
}
return ans;
}
