P2442 Score Statistics

After finishing the league contest, Da Ning successfully avoided the midterm exam, but his homeroom teacher Yellow_sword would not let him off.

Yellow_sword asks Da Ning to build a database to maintain the class exam averages. Each student’s scores for the midterm subjects have been unified into a single rating, an integer in $[1, 100]$. This rating evaluates a student’s overall level. Now Yellow_sword has given Da Ning the average rating of $n$ classes and the size of each class. Because both Yellow_sword and Da Ning are lazy, they will assume every student in a class has a rating equal to that class’s average rating. He wants to know: 1. The average rating of all students over some consecutive classes. 2. The mode of all students’ ratings over some consecutive classes (if there are multiple, output the smallest mode). 3. The range of all students’ ratings over some consecutive classes (that is, the difference between the highest and lowest ratings). Since everyone is lazy, the task is given to you.

The first line contains two integers $n$ and $q$, the number of classes and the number of queries. The second line contains $n$ integers $a_i$, the average rating of the $i$-th class. The third line contains $n$ integers $b_i$, the size of the $i$-th class. The next $q$ lines each contain one query in the format: `Opt u v`. This means to query the item corresponding to $Opt \in [1, 3]$ over classes from $u$ to $v$, as described above.

For each query, output the corresponding result on its own line. For the average, print exactly two decimal places, rounded down (floor).

For $100\%$ of the testdata, it is guaranteed that $1 \le a_i \le 100$, $1 \le b_i \le 100$. | Test point | Scale | Time limit | | :-------: | :----: | :----: | | $1 \sim 3$ | $n = q = 10^3$ | $0.5 \text{ s}$ | | $4 \sim 5$ | $n = q = 5 \times 10^4$ | $0.5 \text{ s}$ | | $6 \sim 7$ | $n = q = 10^5$ | $1 \text{ s}$ | | $8 \sim 10$ | $n = q = 2 \times 10^5$ | $1 \text{ s}$ | It is recommended to use fast I/O. Translated by ChatGPT 5