P8868 [NOIP2022] Competition

Xiao N and Xiao O will take part in the grand programming contest NOIP in November 2022, and Xiao P will serve as the judge. Xiao N and Xiao O each lead a team of $n$ people, and players in each team are numbered from $1$ to $n$. Every player has a programming skill level. Specifically, in Xiao N's team, the player with index $i$ ($1 \leq i \leq n$) has skill level $a _ i$; in Xiao O's team, the player with index $i$ ($1 \leq i \leq n$) has skill level $b _ i$. In particular, $\{a _ i\}$ and $\{b _ i\}$ each form a permutation of $1$ to $n$. Before each match, considering factors such as travel distance and players competing in consecutive matches, Xiao P chooses two parameters $l, r$ ($1 \leq l \leq r \leq n$), meaning that for this match all players whose indices are in $[l, r]$ from both teams will come to the venue to get ready. At the venue, Xiao N and Xiao O will pick parameters $p, q$ by rolling dice ($l \leq p \leq q \leq r$), and only players with indices in $[p, q]$ are eligible to compete. To deliver the most exciting match to the audience, both teams will send the player with the maximum programming skill value whose index lies in $[p, q]$. Suppose Xiao N sends a player with skill $m _ a$, and Xiao O sends a player with skill $m _ b$; then the excitement of the match is $m _ a \times m _ b$. There are $Q$ matches in total in NOIP. For each match, the parameters $l, r$ are fixed, but $p, q$ have not yet been drawn. Xiao P wants to know, for each match, the sum of the excitement values over all possible choices of $p, q$ ($l \leq p \leq q \leq r$). Since the answer can be very large, for each match you only need to output the result modulo $2 ^ {64}$.

The first line contains two positive integers $T, n$, denoting the test point id and the number of participants, respectively. If the input is a sample, it is guaranteed that $T = 0$. The second line contains $n$ positive integers; the $i$-th integer is $a _ i$, the programming skill level of the player with index $i$ in Xiao N's team. The third line contains $n$ positive integers; the $i$-th integer is $b _ i$, the programming skill level of the player with index $i$ in Xiao O's team. The fourth line contains a positive integer $Q$, the number of matches. Each of the next $Q$ lines contains two positive integers $l _ i, r _ i$, the parameters $l, r$ for the $i$-th match.

Output $Q$ lines. The $i$-th line should contain a non-negative integer, which is the sum of the excitement values over all possible matches for the $i$-th query, modulo $2 ^ {64}$.

【Sample 1 Explanation】 When $p = 1, q = 2$, Xiao N will send player $1$, and Xiao O will send player $2$, so the excitement is $2 \times 2 = 4$. When $p = 1, q = 1$, Xiao N will send player $1$, and Xiao O will send player $1$, so the excitement is $2 \times 1 = 2$. When $p = 2, q = 2$, Xiao N will send player $2$, and Xiao O will send player $2$, so the excitement is $1 \times 2 = 2$. 【Sample 2】 This sample satisfies the constraints of test points $1 \sim 2$. 【Sample 3】 This sample satisfies the constraints of test points $3 \sim 5$. 【Constraints】 For all testdata, it is guaranteed that: $1 \leq n, Q \leq 2.5 \times 10 ^ 5$, $1 \leq l _ i \leq r _ i \leq n$, $1 \leq a _ i, b _ i \leq n$, and $\{a _ i\}$ and $\{b _ i\}$ each form a permutation of $1$ to $n$. ::cute-table{tuack} | Test points | $n$ | $Q$ | Special property A | Special property B | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1, 2$ | $\leq 30$ | $\leq 30$ | Yes | Yes | | $3, 4, 5$ | $\leq 3,000$ | $\leq 3,000$ | ^ | ^ | | $6, 7$ | $\leq 10 ^ 5$ | $\leq 5$ | ^ | ^ | | $8, 9$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | ^ | | $10, 11$ | $\leq 10 ^ 5$ | ^ | No | No | | $12, 13$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | ^ | | $14, 15$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | Yes | Yes | | $16, 17$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | | $18, 19$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | ^ | No | | $20, 21$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | | $22, 23$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | No | ^ | | $24, 25$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | Special property A: It is guaranteed that $a$ is a uniformly random permutation of $1 \sim n$. Special property B: It is guaranteed that $b$ is a uniformly random permutation of $1 \sim n$. Translated by ChatGPT 5