Jomax100's blog

Timus problem 2042
By Jomax100, history, 5 years ago, In English

I am working on Segment Trees, and more recently with this implementation by Al.Cash

He brings up this problem but even with the segment tree already built (I assume it stores the number of 'c's in a given range) I don't know how to answer the queries in O(logn). If it's all 'c's then it's easy but what if it's not? Some sort of divide and conquer?

I would appreciate some help with that problem, and recommendations for other good segment tree problems. Preferably on Codeforces (there is no segTree tag; data structures is the closest but it's no guarantee).

Thanks and have a good day!

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jomax100 (previous revision, new revision, compare).

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

Difficulty: 4781

That's all things you need to know about that problem.

If you are trying to learn segment tree, find some easy problems on segment tree. Maybe this one (still not the easiest by far).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I'm not familiar with the difficulty scale on that judge. I can tell it is not the best fit for my current skill, but I am still genuinely curious about the solution! I will follow your advice and try easier problems, but I would love to know how the other problem is solved.

    → Reply