Блог пользователя daihan

What type of problem is this ?

Автор daihan, 8 лет назад, По-английски

Hello codeforces community . I am trying to solve this problem : but dont understand which topics' problem is this . Can anyone tell me ?

Is this a DP problem ?

Problem link : http://agc005.contest.atcoder.jp/tasks/agc005_b

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

range minimum query

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

For each index i find the biggest number r[i] such that min(a[i],..,a[r[i]])=a[i] and the smallest number l[i] such that min(a[l[i]],....,a[i])=a[i].
ans=sigma (r[i]-i+1)*(i-l[i]+1)
r[i] and l[i] can be computed with stacks in O(n).

→ Ответить