Editorial: Looking at Towers (difficult version)
The algorithm is identical to E1 — see the E1 editorial for the full derivation. This note covers only the optimization needed for the harder constraints.
| E1 | E2 | |
|---|---|---|
| $n$ | $\le 5000$ | $\le 3 \times 10^5$ |
| Required complexity | $O(n^2)$ ok | $O(n \log n)$ |
The bottleneck is the range multiply by 2 in the left-chain DP. In E1, iterating over the range naively is fine. In E2, we replace the plain array with a lazy segment tree.
We need three operations on an array $\mathrm{seg}[0..k{-}1]$ (where $k = |H| \le n$):
| Operation | Meaning |
|---|---|
apply(l, r, 2) |
Multiply $\mathrm{seg}[j]$ by 2 for all $j \in [l, r)$ |
get(j) |
Return $\mathrm{seg}[j]$ |
set(j, v) |
Set $\mathrm{seg}[j] := v$ |
The lazy tag is a multiplicative factor (element of $\mathbb{Z}/998244353\mathbb{Z}$):
- Mapping: $f(x) = f \cdot x$.
- Composition: $f \circ g = f \cdot g$.
- Identity: $1$.
The monoid operation op for combining node values is irrelevant (we never issue range queries — only point queries via get), so it can return any dummy value.
In the model solution this is implemented with the Atcoder Library lazy_segtree:
mint op(mint a, mint b) { return mint::raw(0); } // unused
mint e() { return mint::raw(0); }
mint mp(mint f, mint x) { return f * x; } // mapping
mint id() { return mint::raw(1); } // identity
atcoder::lazy_segtree<mint, op, e, mint, mp, mp, id> seg(H.size());
Each element of $A$ triggers one apply ($O(\log n)$) and at most one get + set ($O(\log n)$ each), giving $O(n \log n)$ per test case.
solve: $O(n \log n)$ (segment tree operations).- Combination sweep: $O(n)$.
- Total per test case: $O(n \log n)$.
- Total: $O(\sum n \log n)$.