#include "seats.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
int R[1000010], C[1000010];
int valR[1000010][2], valC[1000010][2];
int N, M, P;
int ans;
int subtask_3;
namespace S3 {
set <int> sx[1010], sy[1010];
int solve(int N, int M) {
vector <pii> A(N+1), B(M+1);
for(int i=1;i<=N+1;i++) A[i-1] = pii(*sx[i].begin(), i);
for(int i=1;i<=M+1;i++) B[i-1] = pii(*sy[i].begin(), i);
sort(all(A)); sort(all(B));
int valr[2] = {A[0].Se, A[0].Se};
int valc[2] = {B[0].Se, B[0].Se};
int res = 0;
for(int i=1, j=1;i<=N;i++) {
while(j <= M && B[j].Fi < A[i].Fi) {
if((valr[1]-valr[0]+1) * (valc[1]-valc[0]+1) == B[j].Fi-1) ++res;
valc[1] = max(valc[1], B[j].Se);
valc[0] = min(valc[0], B[j].Se);
++j;
}
if((valr[1]-valr[0]+1) * (valc[1]-valc[0]+1) == A[i].Fi-1) ++res;
valr[1] = max(valr[1], A[i].Se);
valr[0] = min(valr[0], A[i].Se);
}
return res;
}
}
int check_on_naive(int x) {
return (valR[x][1] - valR[x][0] + 1) * (valC[x][1] - valC[x][0] + 1) == x;
}
void give_initial_chart(int H, int W, std::vector<int> tR, std::vector<int> tC) {
N = H; M = W;
P = N * M;
rep(i, P) R[i + 1] = tR[i] + 1, C[i + 1] = tC[i] + 1;
if(H <= 1000 && W <= 1000) {
subtask_3 = 1;
for(int i=1;i<=P;i++) {
S3::sx[R[i]].insert(i);
S3::sy[C[i]].insert(i);
}
S3::sx[H+1].insert(P+1);
S3::sy[W+1].insert(P+1);
return;
}
valR[0][0] = 1e9, valR[0][1] = -1;
valC[0][0] = 1e9, valC[0][1] = -1;
for(int i=1;i<=P;i++) {
valR[i][0] = min(valR[i-1][0], R[i]);
valR[i][1] = max(valR[i-1][1], R[i]);
valC[i][0] = min(valC[i-1][0], C[i]);
valC[i][1] = max(valC[i-1][1], C[i]);
}
for(int i=1;i<=P;i++) {
ans += check_on_naive(i);
}
}
int swap_seats(int a, int b) {
++a; ++b;
if(a > b) swap(a, b);
if(subtask_3) {
int ra = R[a], rb = R[b];
S3::sx[ra].erase(a); S3::sx[ra].insert(b);
S3::sx[rb].erase(b); S3::sx[rb].insert(a);
int ca = C[a], cb = C[b];
S3::sy[ca].erase(a); S3::sy[ca].insert(b);
S3::sy[cb].erase(b); S3::sy[cb].insert(a);
swap(R[a], R[b]);
swap(C[a], C[b]);
return S3::solve(N, M);
}
if(b-a <= 10000) {
swap(R[a], R[b]);
swap(C[a], C[b]);
for(int i=a;i<b;i++) ans -= check_on_naive(i);
for(int i=a;i<b;i++) {
valR[i][0] = min(valR[i-1][0], R[i]);
valR[i][1] = max(valR[i-1][1], R[i]);
valC[i][0] = min(valC[i-1][0], C[i]);
valC[i][1] = max(valC[i-1][1], C[i]);
ans += check_on_naive(i);
}
return ans;
}
return 0;
}
