programming_monthly

  Codeforces Round 920 (div 3)     Problem F Square root trick, You can use the square root trick to calculate prefix sums in n * sqrt(n).  Where you compute the prefix sums for each step size from 1 to sqrt(n).  Now anytime you have a query where d <= sqrt(n) it can be solved in O(1) with the precomputed prefix sum.  Else it will have sqrt(n) iterations in brute force looping through to get the value.   You do need two prefix sums because you have to create the ones that will give the answer for this specific problem.  Which is a little bit tricky to derive.  Problem G   My approach was very bad for this problem.   You want to use a diagonal prefix sum and column-wise prefix sum.   But the thing is that implementation is very important.   If you try to pad by K to avoid where the diagonal is out of bounds you will end up with 10^5 by 10^5 matrix which is too large.   And if you pad by 1 for the diagonal prefix sum it is a difficult to deal with off by 1 situations.   The