static_range_lis_query.hpp¶
回答静态序列多个子区间的最长严格上升子序列长度，而不必为每个询问重新跑 LIS。
Complexity: Time: O(n log^2 n) preprocessing and O(log n) per query. Space: O(n log n).
AC 记录：static_range_lis_query。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log^2 n) preprocessing and O(log n) per query.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <climits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
namespace static_range_lis_internal {
using uint = unsigned int;
using ll = long long;
static constexpr int wb = CHAR_BIT * sizeof(uint);
inline int popcount(uint val) {
#ifdef __GNUC__
return __builtin_popcount(val);
#else
static_assert(wb == 32);
val -= val >> 1 & 0x55555555;
val = (val & 0x33333333) + (val >> 2 & 0x33333333);
val = val + (val >> 4) & 0x0f0f0f0f;
return val * 0x01010101 >> 24 & 0x3f;
#endif
}
class bit_vector {
struct node {
uint bit = 0;
int sum = 0;
};
std::vector<node> dat;
public:
explicit bit_vector(uint n) : dat(n / wb + 1) {}
void set(uint idx) {
dat[idx / wb].bit |= uint(1) << idx % wb;
dat[idx / wb].sum++;
}
void build() {
for (int i = 1; i < int(dat.size()); i++) {
dat[i].sum += dat[i - 1].sum;
}
}
int rank(uint idx) const {
return dat[idx / wb].sum -
popcount(dat[idx / wb].bit & (~uint(0) << (idx % wb)));
}
int ones() const { return dat.back().sum; }
};
class wavelet_matrix {
template <class Integer> static bool test(Integer val, int bit) {
return (val & (Integer(1) << bit)) != Integer(0);
}
std::vector<bit_vector> lg;
public:
template <class Integer>
wavelet_matrix(int lg0, std::vector<Integer> a)
: lg(lg0, bit_vector(a.size())) {
int n = int(a.size());
std::vector<Integer> z;
z.reserve(n);
for (int bit = lg0 - 1; bit >= 0; bit--) {
bit_vector &dep = lg[bit];
auto one = a.begin();
for (int i = 0; i < n; i++) {
if (test(a[i], bit)) {
dep.set(i);
*one++ = a[i];
} else {
z.push_back(a[i]);
}
}
dep.build();
std::copy(z.begin(), z.end(), one);
z.clear();
}
}
int count_less_than(int l, int r, ll key) const {
int res = r - l;
for (int bit = int(lg.size()) - 1; bit >= 0; bit--) {
const bit_vector &dep = lg[bit];
int rl = dep.rank(l);
int rr = dep.rank(r);
if (test(key, bit)) {
l = rl;
r = rr;
} else {
res -= rr - rl;
int cnt = dep.ones();
l += cnt - rl;
r += cnt - rr;
}
}
return res - (r - l);
}
};
using permutation = std::vector<int>;
using iterator = permutation::iterator;
static constexpr int nil = -1;
inline permutation inverse(const permutation &p) {
permutation res(p.size(), nil);
for (int i = 0; i < int(p.size()); i++) {
if (p[i] != nil) {
res[p[i]] = i;
}
}
return res;
}
inline void unit_monge_distance_product(int n, iterator stk, const iterator arr,
const iterator b) {
if (n == 1) {
stk[0] = 0;
return;
}
const iterator ro0 = stk;
stk += n;
const iterator col = stk;
stk += n;
const auto dfs = [=](int len, const auto &in, const auto &f) {
const iterator ha = stk;
const iterator ma = stk + len;
const iterator hb = stk + 2 * len;
const iterator mb = stk + 3 * len;
const auto cut = [=](const iterator a, iterator hf, iterator map) {
for (int i = 0; i < n; i++) {
if (in(a[i])) {
*hf++ = f(a[i]);
*map++ = i;
}
}
};
cut(arr, ha, ma);
cut(b, hb, mb);
const iterator prd = stk + 4 * len;
unit_monge_distance_product(len, prd, ha, hb);
for (int i = 0; i < len; i++) {
int row = ma[i];
int y = mb[prd[i]];
ro0[row] = y;
col[y] = row;
}
};
int mid = n / 2;
dfs(mid, [mid](int val) { return val < mid; }, [](int val) { return val; });
dfs(
n - mid, [mid](int val) { return val >= mid; },
[mid](int val) { return val - mid; });
struct diagonal_iterator {
int dif = 0;
int y = 0;
};
int row = n;
const auto dr = [&](diagonal_iterator &it) {
if (b[it.y] < mid) {
if (col[it.y] >= row) {
it.dif++;
}
} else if (col[it.y] < row) {
it.dif++;
}
it.y++;
};
const auto up = [&](diagonal_iterator &it) {
if (arr[row] < mid) {
if (ro0[row] >= it.y) {
it.dif--;
}
} else if (ro0[row] < it.y) {
it.dif--;
}
};
diagonal_iterator neg, pos;
while (row != 0) {
while (pos.y != n) {
diagonal_iterator can = pos;
dr(can);
if (can.dif != 0) {
break;
}
pos = can;
}
row--;
up(neg);
up(pos);
while (neg.dif != 0) {
dr(neg);
}
if (neg.y > pos.y) {
ro0[row] = pos.y;
}
}
}
inline permutation subunit_monge_distance_product(permutation arr,
permutation b) {
int n = int(arr.size());
permutation ia = inverse(arr);
permutation ib = inverse(b);
std::swap(b, ib);
permutation ma, mb;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] != nil) {
ma.push_back(i);
arr[n - int(ma.size())] = arr[i];
}
}
std::reverse(ma.begin(), ma.end());
{
int num = 0;
for (int i = 0; i < n; i++) {
if (ia[i] == nil) {
arr[num++] = i;
}
}
}
for (int i = 0; i < n; i++) {
if (b[i] != nil) {
b[mb.size()] = b[i];
mb.push_back(i);
}
}
{
int num = int(mb.size());
for (int i = 0; i < n; i++) {
if (ib[i] == nil) {
b[num++] = i;
}
}
}
permutation buf([](int len) {
int sz = 0;
while (len > 1) {
sz += 2 * len;
len = (len + 1) / 2;
sz += 4 * len;
}
return sz + 1;
}(n));
unit_monge_distance_product(n, buf.begin(), arr.begin(), b.begin());
permutation res(n, nil);
for (int i = 0; i < int(ma.size()); i++) {
int y = buf[n - int(ma.size()) + i];
if (y < int(mb.size())) {
res[ma[i]] = mb[y];
}
}
return res;
}
inline permutation seaweed_doubling(const permutation &p) {
int n = int(p.size());
if (n == 1) {
return {nil};
}
int mid = n / 2;
permutation low, hi, ml, mh;
for (int i = 0; i < n; i++) {
if (p[i] < mid) {
low.push_back(p[i]);
ml.push_back(i);
} else {
hi.push_back(p[i] - mid);
mh.push_back(i);
}
}
low = seaweed_doubling(low);
hi = seaweed_doubling(hi);
permutation pl(n), ph(n);
std::iota(pl.begin(), pl.end(), 0);
std::iota(ph.begin(), ph.end(), 0);
for (int i = 0; i < mid; i++) {
pl[ml[i]] = low[i] == nil ? nil : ml[low[i]];
}
for (int i = 0; mid + i < n; i++) {
ph[mh[i]] = hi[i] == nil ? nil : mh[hi[i]];
}
return subunit_monge_distance_product(std::move(pl), std::move(ph));
}
inline bool is_permutation(const permutation &p) {
std::vector<bool> vis(p.size());
for (int val : p) {
if (val < 0 || val >= int(p.size()) || vis[val]) {
return false;
}
vis[val] = true;
}
return true;
}
inline wavelet_matrix build_wavelet_matrix(const permutation &p) {
assert(is_permutation(p));
int n = int(p.size());
permutation row;
if (n != 0) {
row = seaweed_doubling(p);
}
for (int &val : row) {
if (val == nil) {
val = n;
}
}
int lg0 = 0;
for (int val = n; val > 0; val /= 2) {
lg0++;
}
return wavelet_matrix(lg0, std::move(row));
}
} // namespace static_range_lis_internal
/// @brief Answer LIS lengths on subarrays of a permutation.
/// Seaweed doubling represents semi-local LCS against the sorted permutation
/// as a subunit-Monge permutation. Unit-Monge distance products merge the two
/// halves, and a wavelet matrix over the resulting critical points turns each
/// interval LIS into one orthogonal counting query.
class static_range_lis_query {
int n;
static_range_lis_internal::wavelet_matrix wm;
public:
static_range_lis_query() : static_range_lis_query(std::vector<int>{}) {}
explicit static_range_lis_query(const std::vector<int> &p0)
: n(int(p0.size())),
wm(static_range_lis_internal::build_wavelet_matrix(p0)) {}
int query(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
return (r - l) - wm.count_less_than(l, n, r);
}
};
} // namespace noya
#ifndef NOYA_STATIC_RANGE_LIS_QUERY_HPP
#define NOYA_STATIC_RANGE_LIS_QUERY_HPP 1
/// @complexity Time: O(n log^2 n) preprocessing and O(log n) per query.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <climits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
namespace static_range_lis_internal {
using uint = unsigned int;
using ll = long long;
static constexpr int wb = CHAR_BIT * sizeof(uint);
inline int popcount(uint val) {
#ifdef __GNUC__
return __builtin_popcount(val);
#else
static_assert(wb == 32);
val -= val >> 1 & 0x55555555;
val = (val & 0x33333333) + (val >> 2 & 0x33333333);
val = val + (val >> 4) & 0x0f0f0f0f;
return val * 0x01010101 >> 24 & 0x3f;
#endif
}
class bit_vector {
struct node {
uint bit = 0;
int sum = 0;
};
std::vector<node> dat;
public:
explicit bit_vector(uint n) : dat(n / wb + 1) {}
void set(uint idx) {
dat[idx / wb].bit |= uint(1) << idx % wb;
dat[idx / wb].sum++;
}
void build() {
for (int i = 1; i < int(dat.size()); i++) {
dat[i].sum += dat[i - 1].sum;
}
}
int rank(uint idx) const {
return dat[idx / wb].sum -
popcount(dat[idx / wb].bit & (~uint(0) << (idx % wb)));
}
int ones() const { return dat.back().sum; }
};
class wavelet_matrix {
template <class Integer> static bool test(Integer val, int bit) {
return (val & (Integer(1) << bit)) != Integer(0);
}
std::vector<bit_vector> lg;
public:
template <class Integer>
wavelet_matrix(int lg0, std::vector<Integer> a)
: lg(lg0, bit_vector(a.size())) {
int n = int(a.size());
std::vector<Integer> z;
z.reserve(n);
for (int bit = lg0 - 1; bit >= 0; bit--) {
bit_vector &dep = lg[bit];
auto one = a.begin();
for (int i = 0; i < n; i++) {
if (test(a[i], bit)) {
dep.set(i);
*one++ = a[i];
} else {
z.push_back(a[i]);
}
}
dep.build();
std::copy(z.begin(), z.end(), one);
z.clear();
}
}
int count_less_than(int l, int r, ll key) const {
int res = r - l;
for (int bit = int(lg.size()) - 1; bit >= 0; bit--) {
const bit_vector &dep = lg[bit];
int rl = dep.rank(l);
int rr = dep.rank(r);
if (test(key, bit)) {
l = rl;
r = rr;
} else {
res -= rr - rl;
int cnt = dep.ones();
l += cnt - rl;
r += cnt - rr;
}
}
return res - (r - l);
}
};
using permutation = std::vector<int>;
using iterator = permutation::iterator;
static constexpr int nil = -1;
inline permutation inverse(const permutation &p) {
permutation res(p.size(), nil);
for (int i = 0; i < int(p.size()); i++) {
if (p[i] != nil) {
res[p[i]] = i;
}
}
return res;
}
inline void unit_monge_distance_product(int n, iterator stk, const iterator arr,
const iterator b) {
if (n == 1) {
stk[0] = 0;
return;
}
const iterator ro0 = stk;
stk += n;
const iterator col = stk;
stk += n;
const auto dfs = [=](int len, const auto &in, const auto &f) {
const iterator ha = stk;
const iterator ma = stk + len;
const iterator hb = stk + 2 * len;
const iterator mb = stk + 3 * len;
const auto cut = [=](const iterator a, iterator hf, iterator map) {
for (int i = 0; i < n; i++) {
if (in(a[i])) {
*hf++ = f(a[i]);
*map++ = i;
}
}
};
cut(arr, ha, ma);
cut(b, hb, mb);
const iterator prd = stk + 4 * len;
unit_monge_distance_product(len, prd, ha, hb);
for (int i = 0; i < len; i++) {
int row = ma[i];
int y = mb[prd[i]];
ro0[row] = y;
col[y] = row;
}
};
int mid = n / 2;
dfs(mid, [mid](int val) { return val < mid; }, [](int val) { return val; });
dfs(
n - mid, [mid](int val) { return val >= mid; },
[mid](int val) { return val - mid; });
struct diagonal_iterator {
int dif = 0;
int y = 0;
};
int row = n;
const auto dr = [&](diagonal_iterator &it) {
if (b[it.y] < mid) {
if (col[it.y] >= row) {
it.dif++;
}
} else if (col[it.y] < row) {
it.dif++;
}
it.y++;
};
const auto up = [&](diagonal_iterator &it) {
if (arr[row] < mid) {
if (ro0[row] >= it.y) {
it.dif--;
}
} else if (ro0[row] < it.y) {
it.dif--;
}
};
diagonal_iterator neg, pos;
while (row != 0) {
while (pos.y != n) {
diagonal_iterator can = pos;
dr(can);
if (can.dif != 0) {
break;
}
pos = can;
}
row--;
up(neg);
up(pos);
while (neg.dif != 0) {
dr(neg);
}
if (neg.y > pos.y) {
ro0[row] = pos.y;
}
}
}
inline permutation subunit_monge_distance_product(permutation arr,
permutation b) {
int n = int(arr.size());
permutation ia = inverse(arr);
permutation ib = inverse(b);
std::swap(b, ib);
permutation ma, mb;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] != nil) {
ma.push_back(i);
arr[n - int(ma.size())] = arr[i];
}
}
std::reverse(ma.begin(), ma.end());
{
int num = 0;
for (int i = 0; i < n; i++) {
if (ia[i] == nil) {
arr[num++] = i;
}
}
}
for (int i = 0; i < n; i++) {
if (b[i] != nil) {
b[mb.size()] = b[i];
mb.push_back(i);
}
}
{
int num = int(mb.size());
for (int i = 0; i < n; i++) {
if (ib[i] == nil) {
b[num++] = i;
}
}
}
permutation buf([](int len) {
int sz = 0;
while (len > 1) {
sz += 2 * len;
len = (len + 1) / 2;
sz += 4 * len;
}
return sz + 1;
}(n));
unit_monge_distance_product(n, buf.begin(), arr.begin(), b.begin());
permutation res(n, nil);
for (int i = 0; i < int(ma.size()); i++) {
int y = buf[n - int(ma.size()) + i];
if (y < int(mb.size())) {
res[ma[i]] = mb[y];
}
}
return res;
}
inline permutation seaweed_doubling(const permutation &p) {
int n = int(p.size());
if (n == 1) {
return {nil};
}
int mid = n / 2;
permutation low, hi, ml, mh;
for (int i = 0; i < n; i++) {
if (p[i] < mid) {
low.push_back(p[i]);
ml.push_back(i);
} else {
hi.push_back(p[i] - mid);
mh.push_back(i);
}
}
low = seaweed_doubling(low);
hi = seaweed_doubling(hi);
permutation pl(n), ph(n);
std::iota(pl.begin(), pl.end(), 0);
std::iota(ph.begin(), ph.end(), 0);
for (int i = 0; i < mid; i++) {
pl[ml[i]] = low[i] == nil ? nil : ml[low[i]];
}
for (int i = 0; mid + i < n; i++) {
ph[mh[i]] = hi[i] == nil ? nil : mh[hi[i]];
}
return subunit_monge_distance_product(std::move(pl), std::move(ph));
}
inline bool is_permutation(const permutation &p) {
std::vector<bool> vis(p.size());
for (int val : p) {
if (val < 0 || val >= int(p.size()) || vis[val]) {
return false;
}
vis[val] = true;
}
return true;
}
inline wavelet_matrix build_wavelet_matrix(const permutation &p) {
assert(is_permutation(p));
int n = int(p.size());
permutation row;
if (n != 0) {
row = seaweed_doubling(p);
}
for (int &val : row) {
if (val == nil) {
val = n;
}
}
int lg0 = 0;
for (int val = n; val > 0; val /= 2) {
lg0++;
}
return wavelet_matrix(lg0, std::move(row));
}
} // namespace static_range_lis_internal
/// @brief Answer LIS lengths on subarrays of a permutation.
/// Seaweed doubling represents semi-local LCS against the sorted permutation
/// as a subunit-Monge permutation. Unit-Monge distance products merge the two
/// halves, and a wavelet matrix over the resulting critical points turns each
/// interval LIS into one orthogonal counting query.
class static_range_lis_query {
int n;
static_range_lis_internal::wavelet_matrix wm;
public:
static_range_lis_query() : static_range_lis_query(std::vector<int>{}) {}
explicit static_range_lis_query(const std::vector<int> &p0)
: n(int(p0.size())),
wm(static_range_lis_internal::build_wavelet_matrix(p0)) {}
int query(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
return (r - l) - wm.count_less_than(l, n, r);
}
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_LIS_QUERY_HPP
#include <algorithm>
#include <cassert>
#include <climits>
#include <numeric>
#include <utility>
#include <vector>
/// @complexity Time: O(n log^2 n) preprocessing and O(log n) per query.
/// Space: O(n log n).
namespace noya {
namespace static_range_lis_internal {
using uint = unsigned int;
using ll = long long;
static constexpr int wb = CHAR_BIT * sizeof(uint);
inline int popcount(uint val) {
#ifdef __GNUC__
return __builtin_popcount(val);
#else
static_assert(wb == 32);
val -= val >> 1 & 0x55555555;
val = (val & 0x33333333) + (val >> 2 & 0x33333333);
val = val + (val >> 4) & 0x0f0f0f0f;
return val * 0x01010101 >> 24 & 0x3f;
#endif
}
class bit_vector {
struct node {
uint bit = 0;
int sum = 0;
};
std::vector<node> dat;
public:
explicit bit_vector(uint n) : dat(n / wb + 1) {}
void set(uint idx) {
dat[idx / wb].bit |= uint(1) << idx % wb;
dat[idx / wb].sum++;
}
void build() {
for (int i = 1; i < int(dat.size()); i++) {
dat[i].sum += dat[i - 1].sum;
}
}
int rank(uint idx) const {
return dat[idx / wb].sum -
popcount(dat[idx / wb].bit & (~uint(0) << (idx % wb)));
}
int ones() const { return dat.back().sum; }
};
class wavelet_matrix {
template <class Integer> static bool test(Integer val, int bit) {
return (val & (Integer(1) << bit)) != Integer(0);
}
std::vector<bit_vector> lg;
public:
template <class Integer>
wavelet_matrix(int lg0, std::vector<Integer> a)
: lg(lg0, bit_vector(a.size())) {
int n = int(a.size());
std::vector<Integer> z;
z.reserve(n);
for (int bit = lg0 - 1; bit >= 0; bit--) {
bit_vector &dep = lg[bit];
auto one = a.begin();
for (int i = 0; i < n; i++) {
if (test(a[i], bit)) {
dep.set(i);
*one++ = a[i];
} else {
z.push_back(a[i]);
}
}
dep.build();
std::copy(z.begin(), z.end(), one);
z.clear();
}
}
int count_less_than(int l, int r, ll key) const {
int res = r - l;
for (int bit = int(lg.size()) - 1; bit >= 0; bit--) {
const bit_vector &dep = lg[bit];
int rl = dep.rank(l);
int rr = dep.rank(r);
if (test(key, bit)) {
l = rl;
r = rr;
} else {
res -= rr - rl;
int cnt = dep.ones();
l += cnt - rl;
r += cnt - rr;
}
}
return res - (r - l);
}
};
using permutation = std::vector<int>;
using iterator = permutation::iterator;
static constexpr int nil = -1;
inline permutation inverse(const permutation &p) {
permutation res(p.size(), nil);
for (int i = 0; i < int(p.size()); i++) {
if (p[i] != nil) {
res[p[i]] = i;
}
}
return res;
}
inline void unit_monge_distance_product(int n, iterator stk, const iterator arr,
const iterator b) {
if (n == 1) {
stk[0] = 0;
return;
}
const iterator ro0 = stk;
stk += n;
const iterator col = stk;
stk += n;
const auto dfs = [=](int len, const auto &in, const auto &f) {
const iterator ha = stk;
const iterator ma = stk + len;
const iterator hb = stk + 2 * len;
const iterator mb = stk + 3 * len;
const auto cut = [=](const iterator a, iterator hf, iterator map) {
for (int i = 0; i < n; i++) {
if (in(a[i])) {
*hf++ = f(a[i]);
*map++ = i;
}
}
};
cut(arr, ha, ma);
cut(b, hb, mb);
const iterator prd = stk + 4 * len;
unit_monge_distance_product(len, prd, ha, hb);
for (int i = 0; i < len; i++) {
int row = ma[i];
int y = mb[prd[i]];
ro0[row] = y;
col[y] = row;
}
};
int mid = n / 2;
dfs(mid, [mid](int val) { return val < mid; }, [](int val) { return val; });
dfs(
n - mid, [mid](int val) { return val >= mid; },
[mid](int val) { return val - mid; });
struct diagonal_iterator {
int dif = 0;
int y = 0;
};
int row = n;
const auto dr = [&](diagonal_iterator &it) {
if (b[it.y] < mid) {
if (col[it.y] >= row) {
it.dif++;
}
} else if (col[it.y] < row) {
it.dif++;
}
it.y++;
};
const auto up = [&](diagonal_iterator &it) {
if (arr[row] < mid) {
if (ro0[row] >= it.y) {
it.dif--;
}
} else if (ro0[row] < it.y) {
it.dif--;
}
};
diagonal_iterator neg, pos;
while (row != 0) {
while (pos.y != n) {
diagonal_iterator can = pos;
dr(can);
if (can.dif != 0) {
break;
}
pos = can;
}
row--;
up(neg);
up(pos);
while (neg.dif != 0) {
dr(neg);
}
if (neg.y > pos.y) {
ro0[row] = pos.y;
}
}
}
inline permutation subunit_monge_distance_product(permutation arr,
permutation b) {
int n = int(arr.size());
permutation ia = inverse(arr);
permutation ib = inverse(b);
std::swap(b, ib);
permutation ma, mb;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] != nil) {
ma.push_back(i);
arr[n - int(ma.size())] = arr[i];
}
}
std::reverse(ma.begin(), ma.end());
{
int num = 0;
for (int i = 0; i < n; i++) {
if (ia[i] == nil) {
arr[num++] = i;
}
}
}
for (int i = 0; i < n; i++) {
if (b[i] != nil) {
b[mb.size()] = b[i];
mb.push_back(i);
}
}
{
int num = int(mb.size());
for (int i = 0; i < n; i++) {
if (ib[i] == nil) {
b[num++] = i;
}
}
}
permutation buf([](int len) {
int sz = 0;
while (len > 1) {
sz += 2 * len;
len = (len + 1) / 2;
sz += 4 * len;
}
return sz + 1;
}(n));
unit_monge_distance_product(n, buf.begin(), arr.begin(), b.begin());
permutation res(n, nil);
for (int i = 0; i < int(ma.size()); i++) {
int y = buf[n - int(ma.size()) + i];
if (y < int(mb.size())) {
res[ma[i]] = mb[y];
}
}
return res;
}
inline permutation seaweed_doubling(const permutation &p) {
int n = int(p.size());
if (n == 1) {
return {nil};
}
int mid = n / 2;
permutation low, hi, ml, mh;
for (int i = 0; i < n; i++) {
if (p[i] < mid) {
low.push_back(p[i]);
ml.push_back(i);
} else {
hi.push_back(p[i] - mid);
mh.push_back(i);
}
}
low = seaweed_doubling(low);
hi = seaweed_doubling(hi);
permutation pl(n), ph(n);
std::iota(pl.begin(), pl.end(), 0);
std::iota(ph.begin(), ph.end(), 0);
for (int i = 0; i < mid; i++) {
pl[ml[i]] = low[i] == nil ? nil : ml[low[i]];
}
for (int i = 0; mid + i < n; i++) {
ph[mh[i]] = hi[i] == nil ? nil : mh[hi[i]];
}
return subunit_monge_distance_product(std::move(pl), std::move(ph));
}
inline bool is_permutation(const permutation &p) {
std::vector<bool> vis(p.size());
for (int val : p) {
if (val < 0 || val >= int(p.size()) || vis[val]) {
return false;
}
vis[val] = true;
}
return true;
}
inline wavelet_matrix build_wavelet_matrix(const permutation &p) {
assert(is_permutation(p));
int n = int(p.size());
permutation row;
if (n != 0) {
row = seaweed_doubling(p);
}
for (int &val : row) {
if (val == nil) {
val = n;
}
}
int lg0 = 0;
for (int val = n; val > 0; val /= 2) {
lg0++;
}
return wavelet_matrix(lg0, std::move(row));
}
} // namespace static_range_lis_internal
/// @brief Answer LIS lengths on subarrays of a permutation.
/// Seaweed doubling represents semi-local LCS against the sorted permutation
/// as a subunit-Monge permutation. Unit-Monge distance products merge the two
/// halves, and a wavelet matrix over the resulting critical points turns each
/// interval LIS into one orthogonal counting query.
class static_range_lis_query {
int n;
static_range_lis_internal::wavelet_matrix wm;
public:
static_range_lis_query() : static_range_lis_query(std::vector<int>{}) {}
explicit static_range_lis_query(const std::vector<int> &p0)
: n(int(p0.size())),
wm(static_range_lis_internal::build_wavelet_matrix(p0)) {}
int query(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
return (r - l) - wm.count_less_than(l, n, r);
}
};
} // namespace noya