daihan's blog

What type of problem is this ?

By daihan, 8 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

range minimum query

→ Reply
»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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).

→ Reply