408973: GYM103401 B SVM
Description
SVM loss is a useful loss funtion in machine learning. Assume there are $$$n$$$ training examples and $$$m$$$ classes in a image classification problem. Each training example contains a training image and a label. The label is an integer in range $$$[1,m]$$$.
Our machine learning model takes $$$n$$$ training images as input and outputs $$$n$$$ score vectors of $$$m$$$ dimensions. SVM loss of $$$ith$$$ score vector $$$L_i$$$ is defined as the following formula.
$$$L_i = \sum_{j=1,j \neq label_i}^{m} max(0, S_{i,j}-S_{i,label_i}+Hinge)$$$, where $$$Hinge$$$ is a constant.
We want to accelerate the model training process by calculating the SVM loss function quickly. You need to answer $$$Q$$$ queries asking the sum of SVM loss from $$$lth$$$ score vector to $$$rth$$$ score vector when $$$Hinge$$$ equals $$$h$$$. Formulaly, you need to answer $$$\sum_{i=l}^{r} L_i (Hinge=h)$$$.
InputThe first line contains two integers $$$n,m (1 \leq n*m \leq 10^6)$$$.
The second line contains $$$n$$$ integers, the $$$ith$$$ integer represents $$$label_i (1 \leq label_i \leq m)$$$.
The next $$$n$$$ lines each contains $$$m$$$ integers representing $$$n$$$ score vectors of $$$m$$$ dimensions. The $$$jth$$$ integer of $$$ith$$$ line represents $$$S_{i,j} (-10^9 \leq S_{i,j} \leq 10^9)$$$ which means the $$$jth$$$ element of $$$ith$$$ score vector.
The next line contains an interger $$$Q (1 \leq Q \leq 2*10^5)$$$ representing the number of queries.
The next $$$Q$$$ lines each contains three integers $$$l, r, h (1 \leq l,r \leq n, 0 \leq h \leq 10^9)$$$ having the same meaning in description.
OutputThere are $$$Q$$$ lines in the output, $$$ith$$$ line contains an integer representing the answer of $$$ith$$$ query.
ExampleInput5 3 3 2 3 3 1 6 5 4 8 6 3 4 2 1 3 3 3 5 2 2 8 1 3 0 2 5 0 1 3 1 2 5 1 1 4 2 3 5 2 1 4 3 3 5 3Output
9 6 14 11 23 12 30 16