#include "seats.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
struct chash
{
int operator()(int x) const
{
x ^= (x >> 20) ^ (x >> 12);
return x ^ (x >> 7) ^ (x >> 4);
}
int operator()(long long x) const
{
return x ^ (x >> 32);
}
};
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
template<class T, class U>
T normalize(T x, U mod = 1000000007)
{
return (((x % mod) + mod) % mod);
}
static long long randomizell(long long mod)
{
return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
static int randomize(int mod)
{
return ((1ll << 15) * rand() + rand()) % mod;
}
#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;
#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 1013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
int N, M;
pii pos[MAXN * MAXN * 3];
struct segtree
{
int los[3 * MAXN * MAXN], his[3 * MAXN * MAXN];
void update(int w, int L, int R, int a, int v)
{
if (a < L || R < a)
{
return;
}
if (L == R)
{
los[w] = v;
his[w] = v;
return;
}
int mid = (L + R) >> 1;
update(w << 1, L, mid, a, v);
update(w << 1 | 1, mid + 1, R, a, v);
los[w] = min(los[w << 1], los[w << 1 | 1]);
his[w] = max(his[w << 1], his[w << 1 | 1]);
}
pii query(int w, int L, int R, int a, int b)
{
if (b < L || R < a)
{
return {INF, -INF};
}
if (a <= L && R <= b)
{
return {los[w], his[w]};
}
int mid = (L + R) >> 1;
pii lt = query(w << 1, L, mid, a, b), rt = query(w << 1 | 1, mid + 1, R, a, b);
return {min(lt.fi, rt.fi), max(lt.se, rt.se)};
}
int bound(int w, int L, int R, pii p, int x)
{
//find the first i such that query(0, i) has diff >= x
if (L == R)
{
// cerr << "first time you geq " << x << " is " << L << endl;
return L;
}
int mid = (L + R) >> 1;
pii c = {min(los[w << 1], p.fi), max(his[w << 1], p.se)};
// cerr << p.fi << ' ' << p.se << ' ' << c.fi << ' ' << c.se << ' ' << mid << ' ' << x << endl;
if (c.se - c.fi + 1 >= x)
{
return bound(w << 1, L, mid, p, x);
}
else
{
return bound(w << 1 | 1, mid + 1, R, c, x);
}
}
};
segtree xs, ys;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
N = H;
M = W;
for (int i = 0; i < N * M; i++)
{
pos[i] = {R[i], C[i]};
xs.update(1, 0, N * M - 1, i, R[i]);
ys.update(1, 0, N * M - 1, i, C[i]);
}
}
int solve()
{
int res = 0;
// for (int i = 0; i < N * M; i++)
// {
// pii p = xs.query(1, 0, N * M - 1, 0, i);
// cerr << p.se - p.fi + 1 << ' ';
// }
// cerr << endl;
for (int i = 1; i <= N; i++)
{
//last guy that is <= x
int L = xs.bound(1, 0, N * M - 1, {INF, -INF}, i), R = (i != N ? xs.bound(1, 0, N * M - 1, {INF, -INF}, i + 1) - 1 : N * M - 1);
pii p = xs.query(1, 0, N * M - 1, 0, L);
// assert(L > R || p.se - p.fi + 1 == i);
//L..R, and -1 mod i
for (int j = (L + 1 + i - 1) / i * i - 1; j <= R; j += i)
{
// cerr << "try " << j << endl;
pii y = ys.query(1, 0, N * M - 1, 0, j);
int dy = (y.se - y.fi + 1);
// cerr << dy << endl;
if (dy * i == (j + 1))
{
res++;
// cerr << "yay " << j << endl;
}
}
}
return res;
}
int swap_seats(int a, int b)
{
pii p1 = pos[a], p2 = pos[b];
swap(pos[a], pos[b]);
xs.update(1, 0, N * M - 1, a, pos[a].fi);
ys.update(1, 0, N * M - 1, a, pos[a].se);
xs.update(1, 0, N * M - 1, b, pos[b].fi);
ys.update(1, 0, N * M - 1, b, pos[b].se);
// for (int i = 0; i < N * M; i++)
// {
// cerr << "point " << i << " at " << xs.query(1, 0, N * M - 1, i, i).fi << ' ' << ys.query(1, 0, N * M - 1, i, i).se << endl;
// }
return solve();
}
