For $10\mathrm{\%}$ 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\mathrm{\%}$ 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}+\cdots +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\mathrm{\%}$ 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)$