#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 15e2;
struct nod{
int mn,mx;
}seg[2][4*N*N];
nod operator+(nod a, nod b){
return {min(a.mn,b.mn),max(a.mx,b.mx)};
}
int sz;
void upd(int pos, int x, int y, int l = 0, int r = sz - 1, int node = 1){
if(l == r){
seg[0][node] = {x, x};
seg[1][node] = {y, y};
}else{
int mij = (l + r)/2;
if(pos <= mij){
upd(pos, x, y, l, mij, node*2);
}else{
upd(pos, x, y, mij + 1, r, node*2 + 1);
}
seg[0][node] = seg[0][node*2] + seg[0][node*2 + 1];
seg[1][node] = seg[1][node*2] + seg[1][node*2 + 1];
}
}
pair<nod,nod> operator+(pair<nod,nod> a, pair<nod,nod> b){
return {a.first + b.first, a.second + b.second};
}
pair<nod,nod> query(int ql, int qr, int l = 0, int r = sz - 1, int node = 1){
if(ql <= l && r <= qr){
return {seg[0][node], seg[1][node]};
}else{
int mij = (l + r)/2;
if(qr <= mij){
return query(ql, qr, l, mij, node*2);
}else if(mij <= ql + 1){
return query(ql, qr, mij + 1, r, node*2 + 1);
}else{
return query(ql, qr, l, mij, node*2) + query(ql, qr, mij + 1, r, node*2 + 1);
}
}
}
std::vector<std::vector<int>> v;
vector <int> x,y;
int n,m;
void give_initial_chart(int n2, int m2, std::vector<int> a, std::vector<int> b) {
n = n2;m = m2;
v.assign(n, vector<int>(m,0));
x = a;
y = b;
sz = n*m;
for(int i = 0;i < n*m;i++){
v[x[i]][y[i]] = i;
upd(i, x[i], y[i]);
}
}
int swap_seats(int a, int b){
swap(x[a],x[b]);
swap(y[a],y[b]);
upd(a, x[a], y[a]);
upd(b, x[b], y[b]);
int ans = 0;
/*
int i = 0;
while(i < n*m){
pair<nod,nod> p = query(0, i);
//cout<<p.second.mx<<' '<<p.second.mn<<' '<<p.first.mx<<' '<<p.first.mn<<'\n';
int matrixsz = (p.second.mx - p.second.mn + 1)*(p.first.mx - p.first.mn + 1);
if(matrixsz == i + 1){
ans++;
}
i = max(i + 1, matrixsz - 1);
}
*/
int r = -1,l = m,d = -1,u = n;
for(int i = 0;i < n*m;i++){
l = min(l,y[i]);
r = max(r,y[i]);
u = min(u,x[i]);
d = max(d,x[i]);
if((r - l + 1)*(d - u + 1) == i + 1){
ans++;
}
}
return ans;
}
/**
3 3 63
2 2
1 2
0 2
0 1
0 0
2 1
1 1
1 0
2 0
6 0
5 7
6 4
3 2
0 2
0 2
7 0
7 0
3 2
3 6
0 2
3 5
2 6
2 0
8 6
0 6
1 3
1 8
8 1
4 2
1 8
2 5
1 3
7 0
6 5
6 3
2 8
8 2
1 3
8 5
6 3
8 0
4 8
6 8
7 8
4 3
3 6
5 0
8 5
1 7
2 6
1 2
5 4
5 1
7 6
8 4
7 3
6 8
8 3
0 3
6 3
0 8
0 5
7 2
0 3
7 5
4 5
3 5
1 0
0 8
7 0
2 5
5 8
**/
