結果
| 問題 | No.878 Range High-Element Query |
| ユーザー |
 rsk0315
|
| 提出日時 | 2020-04-26 18:13:08 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 161 ms / 2,000 ms |
| コード長 | 19,209 bytes |
| コンパイル時間 | 1,381 ms |
| コンパイル使用メモリ | 79,952 KB |
| 実行使用メモリ | 11,404 KB |
| 最終ジャッジ日時 | 2024-11-17 16:15:20 |
| 合計ジャッジ時間 | 4,171 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 3 ms
6,820 KB |
| testcase_02 | AC | 3 ms
6,820 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 3 ms
6,816 KB |
| testcase_05 | AC | 3 ms
6,816 KB |
| testcase_06 | AC | 2 ms
6,816 KB |
| testcase_07 | AC | 2 ms
6,816 KB |
| testcase_08 | AC | 3 ms
6,820 KB |
| testcase_09 | AC | 3 ms
6,816 KB |
| testcase_10 | AC | 3 ms
6,816 KB |
| testcase_11 | AC | 146 ms
10,152 KB |
| testcase_12 | AC | 118 ms
10,700 KB |
| testcase_13 | AC | 117 ms
7,832 KB |
| testcase_14 | AC | 90 ms
7,012 KB |
| testcase_15 | AC | 115 ms
10,112 KB |
| testcase_16 | AC | 154 ms
11,188 KB |
| testcase_17 | AC | 160 ms
11,404 KB |
| testcase_18 | AC | 161 ms
11,148 KB |
ソースコード
#line 1 "test/yc_878_reversed.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/878"
#include <cstdio>
#include <algorithm>
#include <vector>
#line 1 "DataStructure/basic_segment_tree.cpp"
/**
* @brief 単一更新セグメント木
* @author えびちゃん
*/
#include <cstddef>
#line 12 "DataStructure/basic_segment_tree.cpp"
template <typename Monoid>
class basic_segment_tree {
public:
using value_type = Monoid;
using size_type = size_t;
private:
std::vector<value_type> M_c;
size_type M_n;
std::vector<size_type> M_covering_segments(size_type l, size_type r) const {
std::vector<size_type> left, right;
l += M_n;
r += M_n;
while (l < r) {
if (l & 1) left.push_back(l++);
if (r & 1) right.push_back(--r);
l >>= 1;
r >>= 1;
}
left.insert(left.end(), right.rbegin(), right.rend());
return left;
}
public:
basic_segment_tree() = default;
explicit basic_segment_tree(size_type n): M_c(n+n), M_n(n) {}
explicit basic_segment_tree(size_type n, value_type const& x):
M_c(n+n, x), M_n(n)
{
for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
}
template <typename InputIt>
basic_segment_tree(InputIt first, InputIt last) {
std::vector<value_type> tmp(first, last);
M_n = tmp.size();
M_c.resize(M_n);
M_c.insert(M_c.end(), tmp.begin(), tmp.end());
for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
}
void assign(size_type n, value_type const& x) {
M_c.assign(n+n, x);
M_n = n;
for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
}
template <typename InputIt>
void assign(InputIt first, InputIt last) {
std::vector<value_type> tmp(first, last);
M_n = tmp.size();
M_c.resize(M_n);
M_c.insert(M_c.end(), tmp.begin(), tmp.end());
for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
}
void set(size_type i, value_type const& x) {
i += M_n;
M_c[i] = x;
while (i > 1) {
i >>= 1;
M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
}
}
void set(size_type i, value_type&& x) {
i += M_n;
M_c[i] = std::move(x);
while (i > 1) {
i >>= 1;
M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
}
}
value_type const& operator [](size_type i) const { return M_c[i + M_n]; }
value_type fold(size_type l, size_type r) const {
value_type resl{}, resr{};
l += M_n;
r += M_n;
while (l < r) {
if (l & 1) resl += M_c[l++];
if (r & 1) resr = M_c[--r] + std::move(resr);
l >>= 1;
r >>= 1;
}
return resl += resr;
}
template <typename Predicate>
size_type foldl_bisect(size_type l, Predicate pred) const {
// Return minimum r such that pred(fold(l, r)) is false,
// or n if such r does not exist.
if (l == M_n) return l;
l += M_n;
size_type r = M_n+M_n;
value_type x{};
size_type h = 0;
auto bisect = [&](size_type v) -> size_type {
while (v < M_n) {
v <<= 1;
if (pred(x + M_c[v])) x += M_c[v++];
}
return v - M_n;
};
for (; l < r; ++h, l >>= 1, r >>= 1) {
if (l & 1) {
if (!pred(x + M_c[l])) return bisect(l);
++l;
}
if (r & 1) --r;
}
for (--h, r <<= 1; r < M_n+M_n; --h, r <<= 1) {
if (((r+1) << h) <= M_n+M_n) {
if (!pred(x + M_c[r])) return bisect(r);
++r;
}
}
return M_n;
}
template <typename Predicate>
size_type foldr_bisect(size_type r, Predicate pred) const {
// Return maximum l such that pred(fold(l, r)) is false,
// of -1 (of size_type) if such does not exist.
if (r == 0) return r;
value_type x{};
size_type v = M_n+M_n;
std::vector<size_type> cs = M_covering_segments(0, r);
std::reverse(cs.begin(), cs.end());
// search the subroot
for (auto s: cs) {
if (!pred(M_c[s] + x)) {
v = s;
break;
}
x = M_c[s] + std::move(x);
}
if (v == M_n+M_n) return -1; // always true
// search the leaf
while (v < M_n) {
v <<= 1;
if (pred(M_c[v|1] + x)) {
x = M_c[v|1] + std::move(x);
} else {
v |= 1;
}
}
return v - M_n;
}
};
#line 1 "DataStructure/wavelet_matrix.cpp"
/**
* @brief ウェーブレット行列
* @author えびちゃん
*/
#line 10 "DataStructure/wavelet_matrix.cpp"
#include <cstdint>
#include <array>
#line 13 "DataStructure/wavelet_matrix.cpp"
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#line 11 "utility/literals.cpp"
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
#line 1 "DataStructure/bit_vector.cpp"
/**
* @brief rank/select 辞書
* @author えびちゃん
*/
#include <climits>
#line 13 "DataStructure/bit_vector.cpp"
#line 15 "DataStructure/bit_vector.cpp"
class bit_vector {
public:
using underlying_type = uintmax_t;
using size_type = size_t;
using difference_type = ptrdiff_t;
private:
static const size_type S_ws = CHAR_BIT * sizeof(underlying_type);
std::vector<underlying_type> M_c;
std::vector<size_type> M_r;
std::vector<size_type> M_s0, M_s1;
std::vector<std::vector<size_type>> M_ss0, M_ss1;
static size_type S_popcount(underlying_type n) {
return __builtin_popcountll(n);
}
static underlying_type S_least_n_bits(size_type n) {
return (1_ju << n) - 1;
}
template <int Bp>
static size_type S_rank_small(underlying_type x, size_type n) {
if (Bp == 0) x = ~x;
return S_popcount(x & S_least_n_bits(n));
}
template <int Bp>
static size_type S_select_small(underlying_type x, size_type n) {
if (n == 0) return 0;
size_type lb = 0;
size_type ub = S_ws;
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
((S_rank_small<Bp>(x, mid) < n)? lb: ub) = mid;
}
return ub;
}
template <int Bp>
size_type M_rank_large(size_type n) const {
// if (n == 0) return 0;
size_type res = M_r[n];
if (Bp == 0) res = n * S_ws - res;
return res;
}
template <int Bp>
void M_prepare_select(std::vector<bool> const& bv,
std::vector<size_type>& s,
std::vector<std::vector<size_type>>& ss) {
size_type z = 0;
size_type n = bv.size();
s.push_back(0);
std::vector<size_type> tmp;
for (size_type i = 0; i < n; ++i) {
if (bv[i] != Bp) continue;
tmp.push_back(i);
if (++z == S_ws) {
size_type len = i+1 - s.back();
s.push_back(i+1);
ss.emplace_back();
if (len >= S_ws * S_ws) ss.back() = std::move(tmp);
tmp.clear();
z = 0;
}
}
ss.push_back(std::move(tmp));
}
template <int Bp>
size_type M_select(size_type n,
std::vector<size_type> const& s,
std::vector<std::vector<size_type>> const& ss) const {
if (n-- == 0) return 0;
size_type j0 = n / S_ws;
size_type j1 = n % S_ws;
if (j0 >= s.size()) return -1_zu;
if (j0+1 == s.size() && j1 >= ss[j0].size()) return -1_zu;
if (!ss[j0].empty()) return ss[j0][j1] + 1;
size_type lb = s[j0] / S_ws;
size_type ub = (j0+1 < s.size())? (s[j0+1]+S_ws-1) / S_ws: M_r.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
((M_rank_large<Bp>(mid) <= n)? lb: ub) = mid;
}
return lb * S_ws + S_select_small<Bp>(M_c[lb], n+1 - M_rank_large<Bp>(lb));
}
public:
bit_vector() = default;
bit_vector(bit_vector const&) = default;
bit_vector(bit_vector&&) = default;
template <typename InputIt>
bit_vector(InputIt first, InputIt last) { assign(first, last); }
bit_vector& operator =(bit_vector const&) = default;
bit_vector& operator =(bit_vector&&) = default;
template <typename InputIt>
void assign(InputIt first, InputIt last) {
std::vector<bool> tmp(first, last);
M_c.resize(tmp.size() / S_ws + 1);
for (size_type i = 0; i < tmp.size(); ++i) {
if (!tmp[i]) continue;
size_type j0 = i / S_ws;
size_type j1 = i % S_ws;
M_c[j0] |= 1_ju << j1;
}
// rank
M_r.assign(M_c.size(), 0);
for (size_type i = 1; i < M_c.size(); ++i)
M_r[i] += M_r[i-1] + S_popcount(M_c[i-1]);
// select
M_prepare_select<0>(tmp, M_s0, M_ss0);
M_prepare_select<1>(tmp, M_s1, M_ss1);
}
size_type rank0(size_type t) const {
return t - rank1(t);
}
size_type rank1(size_type t) const {
size_type j0 = t / S_ws;
size_type j1 = t % S_ws;
return M_r[j0] + S_popcount(S_least_n_bits(j1) & M_c[j0]);
}
size_type rank0(size_type s, size_type t) const {
return (t-s) - rank1(s, t);
}
size_type rank1(size_type s, size_type t) const {
if (s == t) return 0;
return rank1(t) - rank1(s);
}
size_type select0(size_type n) const {
return M_select<0>(n, M_s0, M_ss0);
}
size_type select1(size_type n) const {
return M_select<1>(n, M_s1, M_ss1);
}
size_type select0(size_type n, size_type s) const {
n += rank0(0, s);
return M_select<0>(n, M_s0, M_ss0);
}
size_type select1(size_type n, size_type s) const {
n += rank1(0, s);
return M_select<1>(n, M_s1, M_ss1);
}
};
#line 16 "DataStructure/wavelet_matrix.cpp"
template <size_t Nb, typename Tp = uintmax_t, typename Bv = bit_vector>
class wavelet_matrix {
public:
using value_type = Tp;
using size_type = size_t;
using difference_type = ptrdiff_t;
using bitvector_type = Bv;
private:
std::array<bitvector_type, Nb> M_a = {};
std::array<size_type, Nb> M_z = {};
std::vector<value_type> M_c;
enum S_three_way { S_less = 0, S_equal, S_greater };
static const value_type S_fail = -1; // XXX use std::optional?
size_type M_startpos(value_type x) /* const */ {
size_type s = 0;
size_type t = 0;
for (size_type i = Nb; i-- > 1;) {
size_type j = Nb-i-1;
if (x >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
}
return s;
}
public:
wavelet_matrix() = default;
template <typename InputIt>
wavelet_matrix(InputIt first, InputIt last) { assign(first, last); }
wavelet_matrix(std::initializer_list<value_type> il):
wavelet_matrix(il.begin(), il.end()) {}
template <typename InputIt>
void assign(InputIt first, InputIt last) {
M_c.assign(first, last);
M_z = {{}};
size_type n = M_c.size();
std::vector<value_type> whole = M_c;
for (size_type i = Nb; i--;) {
std::vector<value_type> zero, one;
std::vector<bool> vb(n);
for (size_type j = 0; j < n; ++j) {
((whole[j] >> i & 1)? one: zero).push_back(whole[j]);
vb[j] = (whole[j] >> i & 1);
}
M_z[Nb-i-1] = zero.size();
M_a[Nb-i-1] = bitvector_type(vb.begin(), vb.end());
if (i == 0) break;
whole = std::move(zero);
whole.insert(whole.end(), one.begin(), one.end());
}
}
size_type rank(value_type x, size_type s, size_type t) /* const */ {
if (s == t) return 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
if (x >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
}
return t - s;
}
size_type select(value_type x, size_type n) /* const */ {
if (n == 0) return 0;
if (rank(x, 0, M_c.size()) < n) return -1;
size_type si = M_startpos(x);
if (x & 1) {
n += M_a[Nb-1].rank1(si);
n = M_a[Nb-1].select1(n);
} else {
n += M_a[Nb-1].rank0(si);
n = M_a[Nb-1].select0(n);
}
for (size_type i = 1; i < Nb; ++i) {
size_type j = Nb-i-1;
if (x >> i & 1) {
n -= M_z[j];
n = M_a[j].select1(n);
} else {
n = M_a[j].select0(n);
}
}
return n;
}
size_type select(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
n += rank(x, 0, s);
return select(x, n);
}
std::array<size_type, 3> rank_3way(value_type x,
size_type s, size_type t) /* const */ {
if (s == t) return {0, 0, 0};
size_type lt = 0;
size_type eq = t-s;
size_type gt = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type tmp = t-s;
if (x >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
size_type d = tmp - (t-s);
eq -= d;
((x >> i & 1)? lt: gt) += d;
}
return {lt, eq, gt};
}
std::array<size_type, 3> xored_rank_3way(value_type x, value_type y,
size_type s, size_type t) /* const */ {
if (s == t) return {0, 0, 0};
size_type lt = 0;
size_type eq = t-s;
size_type gt = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type tmp = t-s;
if ((x ^ y) >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
size_type d = tmp - (t-s);
eq -= d;
((y >> i & 1)? lt: gt) += d;
}
return {lt, eq, gt};
}
value_type quantile(size_type k, size_type s, size_type t) /* const */ {
value_type res = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type z = M_a[j].rank0(s, t);
if (k < z) {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
} else {
res |= 1_ju << i;
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
k -= z;
}
}
return res;
}
value_type min_greater(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less] + r3[S_equal];
if (k == t-s) return S_fail;
return quantile(k, s, t);
}
value_type min_greater_equal(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less];
if (k == t-s) return S_fail;
return quantile(k, s, t);
}
value_type max_less(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less];
if (k == 0) return S_fail;
return quantile(k-1, s, t);
}
value_type max_less_equal(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less] + r3[S_equal];
if (k == 0) return S_fail;
return quantile(k-1, s, t);
}
size_type select_greater(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_greater];
((k < n)? lb: ub) = mid;
}
return ub;
}
size_type select_greater_equal(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_equal] + r3[S_greater];
((k < n)? lb: ub) = mid;
}
return ub;
}
size_type select_less(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_less];
((k < n)? lb: ub) = mid;
}
return ub;
}
size_type select_less_equal(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_less] + r3[S_equal];
((k < n)? lb: ub) = mid;
}
return ub;
}
// for dynamic bitvectors only
void insert(size_type t, value_type x) {
size_type s = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
M_a[j].insert(s+t, x >> i & 1);
if (x >> i & 1) {
t = M_a[j].rank(1, s+t+1) - 1;
s = M_z[j];
} else {
t = M_a[j].rank(0, s+t+1) - 1;
s = 0;
++M_z[j];
}
}
}
void erase(size_type t) {
size_type s = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type u = s+t;
if (M_a[j][u]) {
t = M_a[j].rank(1, u+1) - 1;
s = M_z[j];
} else {
t = M_a[j].rank(0, u+1) - 1;
s = 0;
--M_z[j];
}
M_a[j].erase(u);
}
}
void set(size_type t, value_type x) {
erase(t);
insert(t, x);
}
value_type operator [](size_type s) /* const */ {
return quantile(0, s, s+1);
}
};
#line 1 "utility/monoid/max.cpp"
/**
* @brief max を得る演算のモノイド
* @author えびちゃん
*/
#line 10 "utility/monoid/max.cpp"
#include <utility>
#line 1 "utility/limits.cpp"
/**
* @brief 型依存の定数
* @author えびちゃん
*/
#include <limits>
template <typename Tp>
class limits: public std::numeric_limits<Tp> {};
#line 13 "utility/monoid/max.cpp"
template <typename Tp>
class max_monoid {
public:
using value_type = Tp;
private:
value_type M_x = limits<value_type>::min();
public:
max_monoid() = default; // identity
max_monoid(max_monoid const&) = default;
max_monoid(max_monoid&&) = default;
max_monoid(value_type const& x): M_x(x) {};
max_monoid(value_type&& x): M_x(std::move(x)) {};
max_monoid& operator =(max_monoid const&) = default;
max_monoid& operator =(max_monoid&&) = default;
max_monoid& operator +=(max_monoid const& that) {
M_x = std::max(M_x, that.M_x);
return *this;
}
max_monoid& operator +=(max_monoid&& that) {
M_x = std::max(M_x, std::move(that.M_x));
return *this;
}
max_monoid operator +(max_monoid const& that) const {
return max_monoid(*this) += that;
}
max_monoid operator +(max_monoid&& that) const {
return max_monoid(*this) += std::move(that);
}
value_type const& get() const { return M_x; }
};
#line 10 "test/yc_878_reversed.test.cpp"
int main() {
size_t n, q;
scanf("%zu %zu", &n, &q);
std::vector<int> a(n);
for (auto& ai: a) scanf("%d", &ai);
std::reverse(a.begin(), a.end());
basic_segment_tree<max_monoid<int>> st(a.begin(), a.end());
std::vector<size_t> top(n);
for (size_t i = 0; i < n; ++i) {
auto pred = [&](auto x) { return x.get() <= a[i]; };
top[i] = st.foldl_bisect(i, pred);
}
wavelet_matrix<31> wm(top.begin(), top.end());
for (size_t i = 0; i < q; ++i) {
size_t l, r;
scanf(" 1 %zu %zu", &r, &l);
--l, --r;
l = n-1-l;
r = n-1-r;
printf("%zu\n", wm.rank_3way(r, l, r+1)[2]);
}
}