P8991 [Peking University Training 2021] Problem-Setting Expert

CTT2021 D3T2

Alice is an expert at setting problems. Alice sets one problem every day. After $n$ days, she has set $n$ problems. On day $n+1$, Alice does not set a new problem. She plans to choose some problems from the previous $n$ problems to form a contest. For convenience, she decides that the chosen problems must come from a **continuous** time interval, meaning they must be exactly all problems from day $l$ to day $r$ ($1 \le l \le r \le n$). Alice also gives each problem a rating. The rating of the $i$-th problem is $a_i(-1000 \le a_i \le 1001)$. A higher rating means the problem is more about IQ, while a lower rating means it is more about coding. Alice wants the contest to have a distinctive style, i.e., overall leaning toward coding or overall leaning toward IQ. For a contest formed by all problems from day $l$ to day $r$, its distinctiveness is defined as $\Large \frac{(\sum_l^r a_i)^2}{r-l+1}$. Alice wants to **maximize** this distinctiveness. Now, for $m$ queries of the form $ql_i, qr_i$, you need to answer: if Alice is only allowed to choose problems from day $ql_i$ to day $qr_i$, what is the maximum possible distinctiveness of the contest she can form? You need to output this value as a fraction. Since Alice is far too good at setting problems, you may assume that the rating of each problem is **randomly generated**.

The first line contains a positive integer $n$. The second line contains $n$ integers $a_1 \dots a_n$, representing Alice's rating for the problem set on day $i$. The third line contains a positive integer $m$. The next $m$ lines each contain two positive integers $ql_i, qr_i$, representing a query.

Output $m$ lines. Each line contains two integers $p_i, q_i$ with $\gcd(p_i, q_i) = 1$, indicating the answer is $\frac{p_i}{q_i}$. If the answer is $0$, then $p_i = 0$ and $q_i = 1$.

| Subtask | $n=$ | $m=$ | Score | | :-----: | :------: | :------: | :---: | | $1$ | $2000$ | $100000$ | $5$ | | $2$ | $100000$ | $1$ | $15$ | | $3$ | $500000$ | $1$ | $30$ | | $4$ | $100000$ | $5000$ | $15$ | | $5$ | $100000$ | $300000$ | $35$ | For Subtasks $2$ and $3$, all queries satisfy $ql_i = 1$ and $qr_i = n$. All $a_i$ satisfy $-1000 \le a_i \le 1001$. Also, for each $a_i$, the testdata is generated by independently choosing an integer uniformly at random from $[-1000, 1001]$ each time. Translated by ChatGPT 5