#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
struct bit2d {
int n, m;
vector<vector<ll>> bit;
bit2d(int n, int m) : n(n), m(m), bit(n+1, vector<ll>(m+1)) {;;}
void add(int r, int c, ll val) {
r++, c++;
for (; r <= n; r += r & -r) {
for (int i = c; i <= m; i += i & -i) {
bit[r][i] += val;
}
}
}
ll sum(int r, int c) {
r++, c++;
ll res = 0;
for (; r; r -= r & -r) {
for (int i = c; i; i -= i & -i) {
res += bit[r][i];
}
}
return res;
}
ll sum(int r1, int c1, int r2, int c2) {
return sum(r2, c2) - sum(r2, c1-1) - sum(r1-1, c2) + sum(r1-1, c1-1);
}
};
ll h, w;
vector<ll> r, c;
bit2d *st;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H, w = W;
r = vector<ll>(R.begin(), R.end());
c = vector<ll>(C.begin(), C.end());
st = new bit2d(h, w);
for (ll i = 0; i < h * w; i++) {
st->add(r[i], c[i], i);
}
}
bool check(int r1, int c1, int r2, int c2) {
if (r2 < r1) swap(r1, r2);
if (c2 < c1) swap(c1, c2);
ll he = r2 - r1 + 1, we = c2 - c1 + 1;
ll amt = he * we;
ll tri = amt * (amt - 1) / 2;
ll que = st->sum(r1, c1, r2, c2);
// cerr << r1 sp c1 sp r2 sp c2 sp tri sp que << endl;
return tri == que;
}
// to opt: process in linear order (must always eq 0, etc)
int swap_seats(int a, int b) {
// perform swap
{
if (a > b) swap(a, b);
ll diff = b - a;
st->add(r[a], c[a], diff);
st->add(r[b], c[b], -diff);
// cerr << st->sum(r[a], c[a], r[a], c[a]) << endl;
swap(r[a], r[b]);
swap(c[a], c[b]);
}
// count
int res = 0;
for (int r1 = 0; r1 < h; r1++) {
for (int c1 = 0; c1 < w; c1++) {
for (int r2 = r1; r2 < h; r2++) {
for (int c2 = c1; c2 < w; c2++) {
res += check(r1, c1, r2, c2);
// cerr << r1 sp c1 sp r2 sp c2 sp res << endl;
}
}
}
}
return res;
}
