#include "seats.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <set>
using namespace std;
const int INF = 1e8;
const int MX = 4e6 + 10; // maximum hw
int h, w, n;
vector<int> row, col;
int subtask = 6;
// SUBTASK 2
// SUBTASK 3
struct Segtree {
int N, m;
int b[MX], t[MX], l[MX], r[MX];
void setSize(int sz) {
N = sz, m = 1;
while (m < N) m <<= 1;
}
Segtree(int sz) {setSize(sz);}
Segtree() {}
void build() {
for (int i = 0; i < m; ++i) {
if (i >= N) b[i] = l[i] = INF, t[i] = r[i] = -INF;
else {
b[m+i] = t[m+i] = row[i];
l[m+i] = r[m+i] = col[i];
}
}
for (int i = m-1; i > 0; --i) {
b[i] = min(b[2*i], b[2*i+1]);
t[i] = max(t[2*i], t[2*i+1]);
l[i] = min(l[2*i], l[2*i+1]);
r[i] = max(r[2*i], r[2*i+1]);
}
}
void update(int i) {
i += m;
b[i] = t[i] = row[i-m];
l[i] = r[i] = col[i-m];
while (i > 1) {
b[i>>1] = min(b[i], b[i^1]);
t[i>>1] = max(t[i], t[i^1]);
l[i>>1] = min(l[i], l[i^1]);
r[i>>1] = max(r[i], r[i^1]);
i >>= 1;
}
}
pair<pair<int, int>, pair<int, int>> query(int left, int right) {
int B = INF, T = -INF, L = INF, R = -INF;
for (left += m, right += m; left < right; left >>= 1, right >>= 1) {
if (left&1) {
B = min(B, b[left]);
T = max(T, t[left]);
L = min(L, l[left]);
R = max(R, r[left]);
left++;
}
if (right&1) {
--right;
B = min(B, b[right]);
T = max(T, t[right]);
L = min(L, l[right]);
R = max(R, r[right]);
}
}
return {{B, T}, {L, R}};
}
int queryGreater(int type, int limit) { // first index with value past some limit
if (type == 0 && b[1] >= limit) return N;
if (type == 1 && t[1] <= limit) return N;
if (type == 2 && l[1] >= limit) return N;
if (type == 3 && r[1] <= limit) return N;
int i = 1;
while (i < m) {
int left = false;
if (type == 0 && b[2*i] < limit) left = true;
else if (type == 1 && t[2*i] > limit) left = true;
else if (type == 2 && l[2*i] < limit) left = true;
else if (type == 3 && r[2*i] > limit) left = true;
i <<= 1;
if (!left) ++i;
}
return i-m;
}
};
Segtree seg;
// SUBTASK 4
int totalGood = 0;
bool good[MX];
void findGood(int l, int r) { // range [l, r)
for (int i = l; i < r; ++i) {
// find the sidelengths of the segment
auto [p1, p2] = seg.query(0, i+1);
auto [B, T] = p1; auto [L, R] = p2;
totalGood -= good[i];
good[i] = (T-B+1)*(R-L+1)-1 == i;
totalGood += good[i];
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H, w = W, n = H*W, row = R, col = C;
if (n <= 10000) subtask = 2;
else if (h <= 1000 && w <= 1000) {
subtask = 3;
seg.setSize(n);
seg.build();
} else {
subtask = 4;
seg.setSize(n);
seg.build();
findGood(0, n);
}
}
int swap_seats(int A, int B) {
if (subtask == 2) {
swap(row[A], row[B]);
swap(col[A], col[B]);
int beauty = 1;
int b = row[0], t = row[0], l = col[0], r = col[0];
for (int i = 1; i < n; ++i) {
b = min(b, row[i]);
t = max(t, row[i]);
l = min(l, col[i]);
r = max(r, col[i]);
if ((t-b+1)*(r-l+1) == (i+1)) ++beauty;
}
return beauty;
} else if (subtask == 3) {
swap(row[A], row[B]);
swap(col[A], col[B]);
seg.update(A);
seg.update(B);
// main idea: sum of side lengths of good rectangles <= 2000 and strictly increasing
int beauty = 0;
int i = 0;
while (i < n) {
// i is the start of a new segment with equal sidelength sum
// first find the sidelengths of the segment
auto [p1, p2] = seg.query(0, i+1);
auto [B, T] = p1; auto [L, R] = p2;
// now let us find the end of the segment
// i.e. find the first index after i with larger sidelength sum
int nextB = seg.queryGreater(0, B);
int nextT = seg.queryGreater(1, T);
int nextL = seg.queryGreater(2, L);
int nextR = seg.queryGreater(3, R);
int j = min({nextB, nextT, nextL, nextR}); // start of next segment
assert((T-B+1)*(R-L+1)-1 >= j-1);
if ((T-B+1)*(R-L+1)-1 < j) ++beauty;
i = j;
}
return beauty;
} else { // Subtask 4
swap(row[A], row[B]);
swap(col[A], col[B]);
seg.update(A);
seg.update(B);
if (A > B) swap(A, B);
findGood(A, B);
return totalGood;
}
}
