For ~10\%~ of points, we can loop over the numbers ~A_l, A_{l+1}, \dots, A_{r-1}, A_r~ for each query, and find the appropriate difference in ~\mathcal O(N)~.

Time Complexity: ~\mathcal O(NQ)~

For ~60\%~ of points, we have two possible solutions. The first solution involves maintaining a range tree of sorted vectors, and using binary search to answer each query in ~\mathcal O(\log^2 N)~, which can be optimized to ~\mathcal O(\log N)~. The optimization is left as an exercise to the reader.

Time Complexity: ~\mathcal O((N+Q) \log N)~

Another possible solution is to solve the queries using offline processing. We observe that the answer to a query ~q = (l, r, k)~ is the sum ~A_l + A_{l+1} + \dots + A_{r-1} + A_r~ minus twice the sum of all numbers less than ~k~ in the range ~A[l,r]~.

We can compute the first part in ~\mathcal O(1)~, with ~\mathcal O(N)~ preprocessing, using a prefix sum array. To handle the second sum, we can sort all queries by their ~k~ values. We can loop through the values ~i = 0, 1, 2, \dots, \max(A)~, and update a range tree to contain all elements with a value less than or equal to ~i~, and then execute all queries where ~i = k-1~. This results in a time complexity of ~\mathcal O(\log N)~ per update and query.

Time Complexity: ~\mathcal O((N+Q) \log N)~

For the final ~30\%~ of points, we observe that we don't have to loop through ~i = 0, 1, 2, \dots, \max(A)~. Rather, we see that the values of ~A~ and ~k~ are irrelevant when processing offline, and only their relative order matters.

Thus we can remap ~A[1], A[2], \dots, A[N]~ and the ~k~ values of the queries to the numbers ~1, 2, \dots, N+Q~, and solve the problem in the same way as the last subtask.

Time Complexity: ~\mathcal O((N+Q) \log N)~