408973: GYM103401 B SVM

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)$$$.

The 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.

There are $$$Q$$$ lines in the output, $$$ith$$$ line contains an integer representing the answer of $$$ith$$$ query.

5 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 3

9
6
14
11
23
12
30
16