AT_abc480_d.Concatenation of Prefixes

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given an integer sequence (A1,…,AN)(A_1,\dots,A_N) of length NN.

Construct a sequence BB of length N(N+1)2\frac{N(N+1)}{2} by the following procedure.

  • Initially, let BB be an empty sequence.
  • For i=1,2,…,Ni=1,2,\dots,N in this order, append (A1,…,Ai)(A_1,\dots,A_i) to the end of BB.

You are given QQ queries of the following form; answer them.

Query: You are given LL and RR. Find BL+BL+1+⋯+BRB_L+B_{L+1}+\dots+B_R.

给你一个长度为 NN 的整数序列 (A1,…,AN)(A_1,\dots,A_N)。

按如下步骤构造一个长度为 N(N+1)2\frac{N(N+1)}{2} 的序列 BB:

  • 初始时,令 BB 为空序列;
  • 按 i=1,2,…,Ni=1,2,\dots,N 的顺序,将子序列 (A1,…,Ai)(A_1,\dots,A_i) 追加到 BB 的末尾。

现给出 QQ 个如下形式的查询,请回答每个查询。

查询: 给定 LL 和 RR,求 BL+BL+1+⋯+BRB_L+B_{L+1}+\dots+B_R。

输入格式

The input is given from Standard Input in the following format:

NN QQ
A1A_1 A2A_2 …\dots ANA_N
query1\mathrm{query}_1
query2\mathrm{query}_2
⋮\vdots
queryQ\mathrm{query}_Q

Here, queryi\mathrm{query}_i represents the ii-th query and is given in the following format:

LL RR

输入从标准输入中按以下格式给出:

NN QQ
A1A_1 A2A_2 …\dots ANA_N
query1\mathrm{query}_1
query2\mathrm{query}_2
⋮\vdots
queryQ\mathrm{query}_Q

其中,queryi\mathrm{query}_i 表示第 ii 个查询,其格式如下:

LL RR

输出格式

Print QQ lines.
The ii-th line should contain the answer to the ii-th query.

输出 QQ 行。
第 ii 行应包含第 ii 个查询的答案。

输入输出样例

  • 输入#1

    4 3
    1 10 100 1000
    3 6
    1 10
    8 8

    输出#1

    121
    1234
    10
  • 输入#2

    7 1
    100000000 100000000 100000000 100000000 100000000 100000000 100000000
    1 28

    输出#2

    2800000000

说明/提示

Sample 1 Explanation:
B=(1,1,10,1,10,100,1,10,100,1000)B=(1,1,10,1,10,100,1,10,100,1000).

  • The answer to the 11-st query is 10+1+10+100=12110+1+10+100=121.
  • The answer to the 22-nd query is 1+1+10+1+10+100+1+10+100+1000=12341+1+10+1+10+100+1+10+100+1000=1234.
  • The answer to the 33-rd query is 1010.

Constraints

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • −108≤Ai≤108-10^8 \leq A_i \leq 10^8
  • For each query, 1≤L≤R≤N(N+1)21\leq L\leq R \leq \frac{N(N+1)}{2}.
  • All input values are integers.

样例 1 解释:
B=(1,1,10,1,10,100,1,10,100,1000)B=(1,1,10,1,10,100,1,10,100,1000)。

  • 第 11 个查询的答案为 10+1+10+100=12110+1+10+100=121。
  • 第 22 个查询的答案为 1+1+10+1+10+100+1+10+100+1000=12341+1+10+1+10+100+1+10+100+1000=1234。
  • 第 33 个查询的答案为 1010。

约束条件

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • −108≤Ai≤108-10^8 \leq A_i \leq 10^8
  • 对于每个查询,满足 1≤L≤R≤N(N+1)21\leq L\leq R \leq \frac{N(N+1)}{2}。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页