#include "seats.h"
#include <bits/stdc++.h>
#define MAX 10000000
#define lenghttree 4000100
using namespace std;
typedef pair<int,int> ii;
std::vector<ii> r;
int l;
int ma=-1;
vector<int>nodes,vrma,vrmi,vcma,vcmi;
vector<int>treecma(lenghttree),treecmi(lenghttree),treerma(lenghttree),treermi(lenghttree);
void initrmi(int node,int a,int b){
ma=max(ma,node);
if(a==b){
treermi[node]=r[a].first;
}
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 nodea=-1,nodeb=-1;
void query(int node,int a,int b,int p,int q){
if(b<p or a>q) return ;
//cout<<a<<" "<<b<<" "<<node<<endl;
if(a>=p and b<=q){
nodes.push_back(node);
return;
}
query(2*node+1,a,(a+b)/2,p,q);
query(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){
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]);
}
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]);
}
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){
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]);
}
void updatecma(int node, int a,int b,int p,int val){
if(p<a or b<p) return;
if(a==b){
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]);
}
int points=20,beautiful=0;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
vrma.push_back(R[0]);
vrmi.push_back(R[0]);
vcma.push_back(C[0]);
vcmi.push_back(C[0]);
for(int i=0;i<R.size();i++){
if(i!=0){
vrma.push_back(max(R[i],vrma[i-1]));
vrmi.push_back(min(R[i],vrmi[i-1]));
vcma.push_back(max(C[i],vcmi[i-1]));
vcmi.push_back(min(C[i],vcmi[i-1]));
}
if((vrma[i]-vrmi[i]+1)*(vcma[i]-vcmi[i]+1)==i+1){
beautiful++;
}
r.push_back(ii(R[i],C[i]));
}
l=R.size()-1;
initcma(0,0,l);
initcmi(0,0,l);
initrma(0,0,l);
initrmi(0,0,l);
if(H*W<=10000){
points=11;
}
}
int swap_seats(int a, int b) {
if(abs(a-b)<=10000 or points==11){
/*for(int i=0;i<vrma.size();i++){
cout<<vrma[i]<<" ";
}
cout<<endl;*/
for(int i=min(a,b);i<=max(a,b);i++){
if((vrma[i]-vrmi[i]+1)*(vcma[i]-vcmi[i]+1)==i+1){
beautiful--;
}
}
swap(r[a],r[b]);
for(int i=min(a,b);i<=max(a,b);i++){
if(i!=0){
vrma[i]=max(r[i].first,vrma[i-1]);
vrmi[i]=min(r[i].first,vrmi[i-1]);
vcma[i]=max(r[i].second,vcma[i-1]);
vcmi[i]=min(r[i].second,vcmi[i-1]);
}
else{
vrma[i]=r[i].first;
vrmi[i]=r[i].first;
vcma[i]=r[i].second;
vcmi[i]=r[i].second;
}
if((vrma[i]-vrmi[i]+1)*(vcma[i]-vcmi[i]+1)==i+1){
beautiful++;
}
}
/* for(int i=0;i<vrma.size();i++){
cout<<vrma[i]<<" ";
}
cout<<endl;*/
}
else{
int a1,b1;
a1=a;
b1=b;
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);
beautiful=0;
int rmi,rma,cmi,cma;
rma=cma=-1;
rmi=cmi=MAX;
bool sw=0;
for(int i=0;i<r.size();i++){
nodea=-1;nodeb=-1;
nodes.clear();
if(sw==1){
query(0,0,l,0,i);
for(int j=0;j<nodes.size();j++){
rma=max(rma,treerma[nodes[j]]);
cma=max(cma,treecma[nodes[j]]);
rmi=min(rmi,treermi[nodes[j]]);
cmi=min(cmi,treecmi[nodes[j]]);
}
sw=0;
}
else{
rma=max(rma,r[i].first);
rmi=min(rmi,r[i].first);
cma=max(cma,r[i].second);
cmi=min(cmi,r[i].second);
}
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;
sw=1;
}
}
}
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();
}
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
*/
