/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/
#ifndef LOCAL
#include "seats.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
constexpr int INF = 0x3f3f3f3f;
namespace Subtask5{
using PII = pair<int, int>;
int N, M, K;
vector<int> X, Y, V, A;
PII T[1 << 21];
int L[1 << 21];
PII Merge(const PII &l, const PII &r){
return l.x == r.x ? PII(l.x, l.y+r.y) : min(l, r);
}
void Push(int node, int s, int e){
T[node].x += L[node];
if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
L[node] = 0;
}
void Init(int node=1, int s=0, int e=K-1){
if(s == e){ T[node] = {A[s], 1}; return; }
int m = s + e >> 1;
Init(node<<1, s, m);
Init(node<<1|1, m+1, e);
T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Update(int l, int r, int v, int node=1, int s=0, int e=K-1){
Push(node, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
int m = s + e >> 1;
Update(l, r, v, node<<1, s, m);
Update(l, r, v, node<<1|1, m+1, e);
T[node] = Merge(T[node<<1], T[node<<1|1]);
}
int Value(int v){
int pos = Y[v], ret = 0;
ret += (pos == 0 || V[pos-1] > v) ? 1 : -1;
ret += (pos == K-1 || V[pos+1] > v) ? 1 : -1;
return ret;
}
void give_initial_chart(int H, int W, vector<int> &_R, vector<int> &_C){
N = H; M = W; K = N * M;
swap(X, _R); swap(Y, _C);
A.resize(K); V.resize(K);
for(int i=0; i<K; i++) V[Y[i]] = i;
for(int i=0; i<K; i++) A[i] = Value(i);
partial_sum(A.begin(), A.end(), A.begin());
Init();
for(int i=K-1; i>=1; i--) A[i] -= A[i-1];
}
int swap_seats(int a, int b){
swap(Y[a], Y[b]);
swap(V[Y[a]], V[Y[b]]);
for(auto i : {Y[a]-1, Y[a], Y[a]+1, Y[b]-1, Y[b], Y[b]+1}){
if(i < 0 || i >= K) continue;
Update(V[i], K-1, Value(V[i])-A[V[i]]);
A[V[i]] = Value(V[i]);
}
return T[1].y;
}
}
struct Node{
int X1, X2, Y1, Y2;
Node() : Node(INF, -INF, INF, -INF) {}
Node(int x, int y) : Node(x, x, y, y) {}
Node(int X1, int X2, int Y1, int Y2) : X1(X1), Y1(Y1), X2(X2), Y2(Y2) {}
void set(int x, int y){ X1 = X2 = x; Y1 = Y2 = y; }
bool in(const Node &t){
return X1 <= t.X1 && t.X2 <= X2 && Y1 <= t.Y1 && t.Y2 <= Y2;
}
bool check(int sz){
return (X2-X1+1) * (Y2-Y1+1) == sz;
}
};
Node Merge(const Node &l, const Node &r){
return {min(l.X1, r.X1), max(l.X2, r.X2), min(l.Y1, r.Y1), max(l.Y2, r.Y2)};
}
int N, M, K;
vector<int> X, Y;
Node T[1 << 21];
vector<Node> Prefix;
int ans_4;
void Init(int node=1, int s=0, int e=K-1){
if(s == e){ T[node].set(X[s], Y[s]); return; }
int m = s + e >> 1;
Init(node<<1, s, m);
Init(node<<1|1, m+1, e);
T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Update(int pos, int node=1, int s=0, int e=K-1){
if(s == e){ T[node].set(X[s], Y[s]); return; }
int m = s + e >> 1;
if(pos <= m) Update(pos, node<<1, s, m);
else Update(pos, node<<1|1, m+1, e);
T[node] = Merge(T[node<<1], T[node<<1|1]);
}
int Query(Node &data, int node=1, int s=0, int e=K-1){
if(s == e) return (data = Merge(data, T[node])).check(s+1);
if(data.in(T[node])) return data.check(e+1);
int m = s + e >> 1;
return Query(data, node<<1, s, m) + Query(data, node<<1|1, m+1, e);
}
void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C){
N = H; M = W; K = N * M;
if(H == 1){ Subtask5::give_initial_chart(H, W, _R, _C); return; }
swap(X, _R); swap(Y, _C);
if(N <= 1000 && M <= 1000){ Init(); return; } // Subtask3
Prefix.resize(K);
for(int i=0; i<K; i++) Prefix[i].set(X[i], Y[i]);
for(int i=1; i<K; i++) Prefix[i] = Merge(Prefix[i-1], Prefix[i]);
for(int i=0; i<K; i++) ans_4 += Prefix[i].check(i+1);
}
// Subtask 1+2+3+4+5 = 70pts
int swap_seats(int a, int b){
if(N == 1) return Subtask5::swap_seats(a, b);
if(a > b) swap(a, b);
swap(X[a], X[b]); swap(Y[a], Y[b]);
if(N <= 1000 && M <= 1000){ // Subtask3
Update(a); Update(b);
Node data;
return Query(data);
}
for(int i=a; i<b; i++) if(Prefix[i].check(i+1)) ans_4--;
for(int i=a; i<b; i++){
Prefix[i].set(X[i], Y[i]);
if(i) Prefix[i] = Merge(Prefix[i-1], Prefix[i]);
if(Prefix[i].check(i+1)) ans_4++;
}
return ans_4;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int H, W, Q;
cin >> H >> W >> Q;
vector<int> R(H*W), C(H*W);
for(int i=0; i<H*W; i++) cin >> R[i] >> C[i];
vector<int> A(Q), B(Q);
for(int i=0; i<Q; i++) cin >> A[i] >> B[i];
give_initial_chart(H, W, R, C);
for(int i=0; i<Q; i++){
cout << swap_seats(A[i], B[i]) << "\n";
}
return 0;
}
#endif
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
