HackerRank HourRank 25: C. The Strange Function
editorial見ても分からなかったのでkmjpさんのを見た。
editorial中のwith stack
という$2$単語から諸々を読み取るのは私には難しかったです。
problem
長さ$n$の数列$a$が固定される。$a_i \in \mathbb{Z}$であり正とも非負とも限らない。 閉区間$I = [l, r]$に対し$f(I) = (\mathrm{gcd}_{i \in I} a_i) \cdot \left((\sum_{i \in I} a_i) - (\mathrm{max}_{i \in I} a_i) \right)$とおく。 $\mathrm{ans} = \max_I f(I) = \max_{1 \le l \le r \le n} f([l, r])$を答えよ。
solution
区間の右端$r$を固定して左端$l$を伸ばしていったとき$\mathrm{gcd}[l, r) = \mathrm{gcd}_{i \in [l, r)} a_i$の変化する点は高々$\log a_{r-1}$個である。 $\mathrm{gcd}[l, r)$は減るならば常に半分以下に減るためである。 $l \in [l_l, l_r)$において$\mathrm{gcd}[l, r)$が変化しないと分かれば$\mathrm{gcd}[l_l, r) \cdot \max_{l \in [l_l, l_r)} \left( \sum a_i - \max a_i \right)$だけ考えればよい。 変化する点はsegment木やsparse tableにgcdを乗せての二分探索で全て求まる。 $\mathrm{gcd}[l_l, r)$は固定なので、$\max_{l \in [l_l, l_r)} \left( \sum a_i - \max a_i \right)$を効率良く求めればよい。 $n$点でgcdを二分探索するのでこの部分は$O(n \log n \log a_{\mathrm{max}})$。
右端$r$を固定して$b_l = \sum_{i \in [l, r)} a_i - \max_{i \in [l, r)} a_i$とおく。 これを区間加算と区間最大値を処理できる遅延伝播segment木 (つまりstarry sky tree)で管理する。 $r$をひとつ右に増やした場合を考える。 まず和の部分により全体に$a_{r - 1}$を加算。 最大値の部分が難しいがslide最小値と同様のテクを使う。 最大値の変化する点をstackに持っておき、このstackからのpopに合わせてsegment木に対する区間加算クエリを発行する。 このpopの回数はpushの回数で抑えられて全体で合計高々$N$回。 segment木の構築や更新でこの部分は$O(n \log n)$。
ちなみに$\mathrm{gcd}[l_l, r)$が$l_l$を減らすに従って単調減少することから、$\min_{l \in [l_l, l_r)} b_l$でなくて$\min_{l \in [l_l, r)} b_l$だけ求めるのでも十分。 これを使うと実装が楽になる。
注意
- gcdの変化する点だけ見ればよいというのは嘘。 $a + b + c - \max \{ a, b, c \} \ge a + b - \max \{ a, b \}$は一般に成り立たないため。 変形すると$c + \max \{ a, b \} \ge \max \{ a, b, c \}$で、例えば$c$が負の場合には偽になる。
- 愚直解を書いて適当に打ち切るだけでほとんど満点が得られる。 ジャッジ特性により入力解析も楽なのでそのまま押し込めるはず。
implementation
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using ll = long long;
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }
template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
assert (l <= r);
-- l;
while (r - l > 1) {
int64_t m = l + (r - l) / 2; // avoid overflow
(p(m) ? r : l) = m;
}
return r;
}
template <typename T>
T gcd(T a, T b) {
while (a) {
b %= a;
swap(a, b);
}
return abs(b);
}
template <class Semilattice>
struct sparse_table {
typedef typename Semilattice::underlying_type underlying_type;
vector<vector<underlying_type> > table;
Semilattice lat;
sparse_table() = default;
sparse_table(vector<underlying_type> const & data, Semilattice const & a_lat = Semilattice())
: lat(a_lat) {
int n = data.size();
int log_n = 32 - __builtin_clz(n);
table.resize(log_n, vector<underlying_type>(n));
table[0] = data;
REP (k, log_n - 1) {
REP (i, n) {
table[k + 1][i] = i + (1ll << k) < n ?
lat.append(table[k][i], table[k][i + (1ll << k)]) :
table[k][i];
}
}
}
underlying_type range_concat(int l, int r) const {
if (l == r) return lat.unit(); // if there is no unit, remove this line
assert (0 <= l and l < r and r <= table[0].size());
int k = 31 - __builtin_clz(r - l); // log2
return lat.append(table[k][l], table[k][r - (1ll << k)]);
}
};
struct gcd_semilattice {
typedef int underlying_type;
int unit() const { return 0; }
int append(int a, int b) const { return gcd(a, b); }
};
template <class Monoid, class OperatorMonoid>
struct lazy_propagation_segment_tree { // on monoids
static_assert (is_same<typename Monoid::underlying_type, typename OperatorMonoid::target_type>::value, "");
typedef typename Monoid::underlying_type underlying_type;
typedef typename OperatorMonoid::underlying_type operator_type;
const Monoid mon;
const OperatorMonoid op;
int n;
vector<underlying_type> a;
vector<operator_type> f;
lazy_propagation_segment_tree() = default;
lazy_propagation_segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid(), OperatorMonoid const & a_op = OperatorMonoid())
: mon(a_mon), op(a_op) {
n = 1; while (n <= a_n) n *= 2;
a.resize(2 * n - 1, mon.unit());
fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
f.resize(max(0, (2 * n - 1) - n), op.identity());
}
void range_apply(int l, int r, operator_type z) {
assert (0 <= l and l <= r and r <= n);
range_apply(0, 0, n, l, r, z);
}
void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
if (l <= il and ir <= r) { // 0-based
a[i] = op.apply(z, a[i]);
if (i < f.size()) f[i] = op.compose(z, f[i]);
} else if (ir <= l or r <= il) {
// nop
} else {
range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
f[i] = op.identity();
range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
}
}
underlying_type range_concat(int l, int r) {
assert (0 <= l and l <= r and r <= n);
return range_concat(0, 0, n, l, r);
}
underlying_type range_concat(int i, int il, int ir, int l, int r) {
if (l <= il and ir <= r) { // 0-based
return a[i];
} else if (ir <= l or r <= il) {
return mon.unit();
} else {
return op.apply(f[i], mon.append(
range_concat(2 * i + 1, il, (il + ir) / 2, l, r),
range_concat(2 * i + 2, (il + ir) / 2, ir, l, r)));
}
}
};
struct max_monoid {
typedef ll underlying_type;
ll unit() const { return LLONG_MIN; }
ll append(ll a, ll b) const { return max(a, b); }
};
struct plus_operator_monoid {
typedef ll underlying_type;
typedef ll target_type;
ll identity() const { return 0; }
ll apply(underlying_type a, target_type b) const { return a + b; }
ll compose(underlying_type a, underlying_type b) const { return a + b; }
};
typedef lazy_propagation_segment_tree<max_monoid, plus_operator_monoid> starry_sky_tree;
constexpr ll inf = ll(1e18) + 9;
int main() {
// input
int n; scanf("%d", &n);
vector<int> a(n); REP (i, n) scanf("%d", &a[i]);
// solve
ll result = - inf;
sparse_table<gcd_semilattice> table(a);
starry_sky_tree segtree(n, 0);
stack<pair<int, int> > stk;
REP3 (r, 1, n + 1) {
// update the segment tree
segtree.range_apply(0, r, a[r - 1]);
{ // update the stack
int l = r - 1;
while (not stk.empty() and stk.top().second <= a[r - 1]) {
int nl, value; tie(nl, value) = stk.top(); stk.pop();
segtree.range_apply(nl, l, value - a[r - 1]);
l = nl;
}
segtree.range_apply(r - 1, r, - a[r - 1]);
stk.emplace(l, a[r - 1]);
}
{ // update the result
int l = r;
while (l > 0) {
int d = table.range_concat(l - 1, r);
l = binsearch(0, l, [&](int m) {
return table.range_concat(m, r) >= d;
});
chmax(result, d * segtree.range_concat(l, r));
}
}
}
// output
printf("%lld\n", result);
return 0;
}