P8991 [北大集训 2021] 出题高手

题目背景

CTT2021 D3T2

题目描述

Alice 是一个出题高手。 Alice 每天都会出一道题,这样 $n$ 天过去,她就出了 $n$ 道题了。 第 $n+1$ 天,Alice 没有出题,她打算从之前的 $n$ 道题中选择若干道组成一个比赛。方便起见,她决定这些选择的题目得是**连续**的一个时间段出的,也就是这些题目必须形如:第 $l$ 天到第 $r$ 天出的所有题目($1\le l \le r \le n$)。 Alice 还给每个题目一个评分,第 $i$ 个题目的评分为 $a_i(-1000 \le a_i \le 1001)$ ,评分越高代表这道题越偏智商,评分越低说明这道题越偏码力。 Alice 希望组成的比赛具备特色,也即整体偏向代码或者整体偏向智商。一场以 Alice 第 $l$ 天到第 $r$ 天出的题目组成的比赛的特色程度定义为 $\Large \frac{(\sum_l^r a_i)^2}{r-l+1}$ ,Alice 想要**最大化**这个特色程度。 现在,对于 $m$ 个形如 $ql_i,qr_i$ 的询问,你需要回答如果将 Alice 能选择的题目限定在第 $ql_i$ 到 $qr_i$ 天出的题,Alice 能组成的特色程度最大的比赛的特色程度是多少,你需要以分数的形式输出这个特色程度。 由于 Alice 出题的水平过于高超,你可以认为每道题的评分是**随机生成**的。

输入格式

输出格式

说明/提示

| 子任务 | $n=$ | $m=$ | 分值 | | :----: | :------: | :------: | :--: | | $1$ | $2000$ | $100000$ | $5$ | | $2$ | $100000$ | $1$ | $15$ | | $3$ | $500000$ | $1$ | $30$ | | $4$ | $100000$ | $5000$ | $15$ | | $5$ | $100000$ | $300000$ | $35$ | 对于 第 $2$ 个和第 $3$ 个子任务,保证所有询问满足 $ql_i = 1$,$qr_i = n$。 所有的 $a_i$ 保证满足 $-1000 \le a_i \le 1001$。且对于 $a_i$ ,数据生成方式为每次独立地从 $[-1000,1001]$ 中等概率随机选取一个整数。