Sure, sorry if it wasn't clear initially. The main goal is just to get rid of the modulo because that would mean we have to calculate each interval individually which is O(N^2). If we fix the right end point and use prefix sums modulo M to express the sum of an interval, if the prefix sum for the left is greater than the right we will have a negative sum mod M, so we add M. With the appropriate datastructure (Fenwick Tree) we can update our list of prefix sum values and also find how many are greater than some value, both in logarithmic time, which is fast enough. A Fenwick Tree basically stores sums of different intervals of an array efficiently such that by adding them together we are able to find the sum of any interval in O(log N) time. If we use a Fenwick Tree to count the number of times a prefix sum has appeared (mod M), then the sum from R + 1 to M will be the number of elements that are greater than R, which is calculated in O(log M) times in this problem. Hope this helps!
кто тебе дал клавиатуру, о боже.. Просто магические названия переменных, причем глобальных переменных, и при этом зачем тебе вообще signed тип вместо ing или вообще какого-нибудь long long. еще и макрос ключевого слова
just read the editorial if you have an issue (though the official solutions are often like this), cheers in my bigger projects of course I keep good principles with my formatting/names etc. but this type of stuff I just need to know what's going on
can you tell me what are you tryin to do in q uestion E . i can not understand any thing
Sure, sorry if it wasn't clear initially. The main goal is just to get rid of the modulo because that would mean we have to calculate each interval individually which is O(N^2).
If we fix the right end point and use prefix sums modulo M to express the sum of an interval, if the prefix sum for the left is greater than the right we will have a negative sum mod M, so we add M. With the appropriate datastructure (Fenwick Tree) we can update our list of prefix sum values and also find how many are greater than some value, both in logarithmic time, which is fast enough.
A Fenwick Tree basically stores sums of different intervals of an array efficiently such that by adding them together we are able to find the sum of any interval in O(log N) time. If we use a Fenwick Tree to count the number of times a prefix sum has appeared (mod M), then the sum from R + 1 to M will be the number of elements that are greater than R, which is calculated in O(log M) times in this problem. Hope this helps!
i think you should lower the background music
ok in the next one
кто тебе дал клавиатуру, о боже.. Просто магические названия переменных, причем глобальных переменных, и при этом зачем тебе вообще signed тип вместо ing или вообще какого-нибудь long long. еще и макрос ключевого слова
just read the editorial if you have an issue (though the official solutions are often like this), cheers
in my bigger projects of course I keep good principles with my formatting/names etc. but this type of stuff I just need to know what's going on
dont hate on my glorious king like that 💔