Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage
  1. Home
  2. /
  3. Codeforces
  4. /
  5. Contests
  6. /
  7. Educational Codeforces Round 182 (Rated for Div. 2)
  8. /
  9. E2. Looking at Towers (difficult version)
  10. /
  11. Hints: Looking at Towers (difficult version)

Hints: Looking at Towers (difficult version)

The algorithmic idea is identical to E1. The only difference is the constraints ($n \le 3 \times 10^5$ instead of $n \le 5000$), which demands an $O(n \log n)$ implementation. Read the E1 hints first if you haven’t.

The solution decomposes into:

  1. A left-chain DP computing $L[i]$ = number of partial subsequences preserving $L(a)$ whose last “advancing” position is $i$.
  2. A symmetric right-chain DP for $R[i]$.
  3. A combination sweep over global-max positions.

The bottleneck is the left-chain DP, which at each element does a range multiply by 2 and a point query + point update on an array indexed by prefix maxima levels.

For E1, a naive $O(n)$ range multiply per element gives $O(n^2)$ total — fine for $n \le 5000$.

For E2, you need the range multiply in $O(\log n)$. What data structure supports range-multiply and point-query?

Answer to Hint 2: A lazy segment tree with:

  • Lazy tag = multiplicative factor (mint).
  • apply(l, r, 2) = multiply all entries in $[l, r)$ by 2.
  • get(j) = point query at index $j$.
  • set(j, v) = point update at index $j$.

The Atcoder Library lazy_segtree supports exactly this. The monoid op for combining values is unused (we never do range queries), so it can return anything. The mapping and composition are both multiplication.

This gives $O(n \log n)$ per test case.