AT_abc480_d.Concatenation of Prefixes
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an integer sequence (A1,…,AN) of length N.
Construct a sequence B of length 2N(N+1) by the following procedure.
- Initially, let B be an empty sequence.
- For i=1,2,…,N in this order, append (A1,…,Ai) to the end of B.
You are given Q queries of the following form; answer them.
Query: You are given L and R. Find BL+BL+1+⋯+BR.
给你一个长度为 N 的整数序列 (A1,…,AN)。
按如下步骤构造一个长度为 2N(N+1) 的序列 B:
- 初始时,令 B 为空序列;
- 按 i=1,2,…,N 的顺序,将子序列 (A1,…,Ai) 追加到 B 的末尾。
现给出 Q 个如下形式的查询,请回答每个查询。
查询: 给定 L 和 R,求 BL+BL+1+⋯+BR。
输入格式
The input is given from Standard Input in the following format:
N Q
A1 A2 … AN
query1
query2
⋮
queryQ
Here, queryi represents the i-th query and is given in the following format:
L R
输入从标准输入中按以下格式给出:
N Q
A1 A2 … AN
query1
query2
⋮
queryQ
其中,queryi 表示第 i 个查询,其格式如下:
L R
输出格式
Print Q lines.
The i-th line should contain the answer to the i-th query.
输出 Q 行。
第 i 行应包含第 i 个查询的答案。
输入输出样例
输入#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).
- The answer to the 1-st query is 10+1+10+100=121.
- The answer to the 2-nd query is 1+1+10+1+10+100+1+10+100+1000=1234.
- The answer to the 3-rd query is 10.
Constraints
- 1≤N≤105
- 1≤Q≤105
- −108≤Ai≤108
- For each query, 1≤L≤R≤2N(N+1).
- All input values are integers.
样例 1 解释:
B=(1,1,10,1,10,100,1,10,100,1000)。
- 第 1 个查询的答案为 10+1+10+100=121。
- 第 2 个查询的答案为 1+1+10+1+10+100+1+10+100+1000=1234。
- 第 3 个查询的答案为 10。
约束条件
- 1≤N≤105
- 1≤Q≤105
- −108≤Ai≤108
- 对于每个查询,满足 1≤L≤R≤2N(N+1)。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?