#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
vector<int> S;
int len = 1;
SegmentTree(int n){
while(len < n) len <<= 1;
S.resize(2*len);
}
void upd(int i, int v){
i += len;
S[i] = max(S[i],v);
for(i /= 2; i > 0; i /= 2){
S[i] = max(S[i*2],S[i*2+1]);
}
}
int query(int ql, int qr, int l = 0,int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return -1;
int mid = (l+r)/2;
return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
}
};
vector<int> r, c;
vector<vector<int>> grid;
int h, w;
int n;
void give_initial_chart(int Hi, int Wi, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
h = Hi;
w = Wi;
n = h*w;
grid = vector<vector<int>>(h, vector<int>(w));
for(int i = 0; i < n; i++){
grid[r[i]][c[i]] = i;
}
}
int swap_seats(int a, int b) {
swap(grid[r[a]][c[a]], grid[r[b]][c[b]]);
swap(c[a],c[b]);
swap(r[a],r[b]);
int wl = c[0];
int wr = c[0];
int hl = r[0];
int hr = r[0];
SegmentTree seg(h);
int cnt = 0;
for(int j = 0; j < h; j++){
seg.upd(j, grid[j][wl]);
}
for(int i = 0; i < n; i++){
int nextW = c[i];
int nextH = r[i];
while(nextW < wl){
for(int j = 0; j < h; j++){
seg.upd(j, grid[j][wl-1]);
}
wl--;
}
while(nextW > wr){
for(int j = 0; j < h; j++){
seg.upd(j, grid[j][wr+1]);
}
wr++;
}
hl = min(hl, r[i]);
hr = max(hr, r[i]);
int q = seg.query(hl,hr+1);
if(q == i) {
cnt++;
}
}
return cnt;
}
