#include "seats.h"
#include <bits/stdc++.h>
#define MAX 100000000
#define lenghttree 4000100
using namespace std;
typedef pair<int,int> ii;
std::vector<ii> r;
int l,ma=-1;
int treermi[lenghttree],treerma[lenghttree],treecmi[lenghttree],treecma[lenghttree];
void initrmi(int node,int a,int b){
// ma=max(ma,node);
if(a==b){
// //<<a<<" "<<r[a].first<<" node: "<<node<<endl;
treermi[node]=r[a].first;
// return;
}
else{
initrmi(2*node+1,a,(a+b)/2);
initrmi(2*node+2,(a+b)/2+1,b);
treermi[node]=min(treermi[2*node+1],treermi[2*node+2]);
}
}
int queryrmi(int node,int a,int b,int p,int q){
if(q<a or b<p) return MAX;
if(p<=a and b<=q) return treermi[node];
return min(queryrmi(2*node+1,a,(a+b)/2,p,q),queryrmi(2*node+2,(a+b)/2+1,b,p,q));
}
void updatermi(int node,int a,int b,int p,int val){
if(p<a or b<p) return;
if(a==b){
//<<a<<" "<<val<<" node: "<<node<<endl;
treermi[node]=val;
return;
}
updatermi(2*node+1,a,(a+b)/2,p,val);
updatermi(2*node+2,(a+b)/2+1,b,p,val);
treermi[node]=min(treermi[2*node+1],treermi[2*node+2]);
}
void initrma(int node,int a,int b){
if(a==b){
treerma[node]=r[a].first;
return;
}
initrma(2*node+1,a,(a+b)/2);
initrma(2*node+2,(a+b)/2+1,b);
treerma[node]=max(treerma[2*node+1],treerma[2*node+2]);
}
int queryrma(int node,int a,int b,int p,int q){
if(q<a or b<p) return -1;
if(p<=a and b<=q) return treerma[node];
return max(queryrma(2*node+1,a,(a+b)/2,p,q), queryrma(2*node+2,(a+b)/2+1,b,p,q));
}
void updaterma(int node,int a,int b,int p,int val){
if(p<a or b<p) return;
if(a==b){
treerma[node]=val;
return;
}
updaterma(2*node+1,a,(a+b)/2,p,val);
updaterma(2*node+2,(a+b)/2+1,b,p,val);
treerma[node]=max(treerma[2*node+1],treerma[2*node+2]);
}
void initcmi(int node,int a,int b){
if(a==b){
treecmi[node]=r[a].second;
return;
}
initcmi(2*node+1,a,(a+b)/2);
initcmi(2*node+2,(a+b)/2+1,b);
treecmi[node]=min(treecmi[2*node+1],treecmi[2*node+2]);
}
int querycmi(int node,int a,int b,int p,int q){
if(q<a or b<p) return MAX;
if(p<=a and b<=q) return treecmi[node];
return min(querycmi(2*node+1,a,(a+b)/2,p,q),querycmi(2*node+2,(a+b)/2+1,b,p,q));
}
void updatecmi(int node,int a,int b,int p,int val){
if(p<a or b<p) return;
if(a==b){
treecmi[node]=val;
return;
}
updatecmi(2*node+1,a,(a+b)/2,p,val);
updatecmi(2*node+2,(a+b)/2+1,b,p,val);
treecmi[node]=min(treecmi[2*node+1],treecmi[2*node+2]);
}
void initcma(int node,int a,int b){
////<<a<<" "<<b<<endl;
if(a==b){
treecma[node]=r[a].second;
return;
}
initcma(2*node+1,a,(a+b)/2);
initcma(2*node+2,(a+b)/2+1,b);
treecma[node]=max(treecma[2*node+1],treecma[2*node+2]);
}
int querycma(int node,int a,int b,int p,int q){
if(q<a or b<p) return -1;
if(p<=a and b<=q) return treecma[node];
return max(querycma(2*node+1,a,(a+b)/2,p,q), querycma(2*node+2,(a+b)/2+1,b,p,q));
}
void updatecma(int node, int a,int b,int p,int val){
if(p<a or b<p) return;
if(a==b){//<<a<<" "<<b<<" "<<node<<" "<<val<<endl;
treecma[node]=val;
return;
}
updatecma(2*node+1,a,(a+b)/2,p,val);
updatecma(2*node+2,(a+b)/2+1,b,p,val);
treecma[node]=max(treecma[2*node+1],treecma[2*node+2]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
//<<endl;
for(int i=0;i<R.size();i++){
r.push_back(ii(R[i],C[i]));
}
/*for(int i=0;i<R.size();i++){
//<<r[i].first<<" "<<r[i].second<<endl;
}*/
l=R.size()-1;
initcma(0,0,l);
////<<l<<endl;
initcmi(0,0,l);
initrma(0,0,l);
initrmi(0,0,l);
/*for(int i=0;i<ma;i++){
//<<treermi[i]<<" ";
}
//<<endl;*/
}
int swap_seats(int a, int b) {
int beautiful=0,a1,b1;
a1=a;
b1=b;
/*for(int i=0;i<ma;i++){
cout<<treecma[i]<<" ";
}
cout<<endl;*/
updatecma(0,0,l,a1,r[b1].second);
updatecma(0,0,l,b1,r[a1].second);
updatecmi(0,0,l,b1,r[a1].second);
updatecmi(0,0,l,a1,r[b1].second);
updaterma(0,0,l,a1,r[b1].first);
updaterma(0,0,l,b1,r[a1].first);
updatermi(0,0,l,a1,r[b1].first);
updatermi(0,0,l,b1,r[a1].first);
////<<r[a1].first<<" "<<r[b1].second<<" "<<a1<<" "<<b1<<endl;
/*for(int i=0;i<ma;i++){
cout<<treecma[i]<<" ";
}
cout<<endl<<endl;*/
swap(r[a],r[b]);
int rmi,rma,cmi,cma;
rma=cma=-1;
rmi=cmi=MAX;
for(int i=0;i<r.size();i++){
rmi=min(rmi,r[i].first);
cmi=min(cmi,r[i].second);
rma=max(rma,r[i].first);
cma=max(cma,r[i].second);
/*rmi=queryrmi(0,0,l,0,i);
cmi=querycmi(0,0,l,0,i);
rma=queryrma(0,0,l,0,i);
cma=querycma(0,0,l,0,i);*/
if((rma-rmi+1)*(cma-cmi+1)==i+1){
beautiful++;
}
/*if((rma-rmi+1)*(cma-cmi+1)>i+1){
i=(rma-rmi+1)*(cma-cmi+1)-2;
}*/
//printf("cmi: %d cma: %d rmi: %d rma: %d i: %d i+1: %d== %d\n",cmi,cma,rmi,rma,i,i+1,(rma-rmi+1)*(cma-cmi+1));
}
// swap(r[a],r[b]);
return beautiful;
}
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
cout<<"Final"<<endl;
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; j++) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}*/
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
/*
3
4
*/
