Timus problem 2042

Revision en3, by Jomax100, 2019-09-03 14:22:28

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!

Tags #segment tree, #learning

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Jomax100 2019-09-03 14:22:28 87 (published)
en2 English Jomax100 2019-09-03 14:21:08 13 Tiny change: 'by [user:AI.Cash]\n\n' -> 'by [user:Al.Cash]\n\n'
en1 English Jomax100 2019-09-03 14:20:24 635 Initial revision (saved to drafts)