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!
Auto comment: topic has been updated by Jomax100 (previous revision, new revision, compare).
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).
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.