首页 > 试题广场 >

消消乐

[编程题]消消乐
  • 热度指数:5 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现在有一个长度为 2^k 的序列 A,此序列下标从 1 开始,且对于序列内的任一元素,均大于等于零,且小于等于九。对于该序列,可以进行一轮合并操作,对于 0 <= i < 2^(k-1),将 A[2*i+1],A[2*i+2] 替换为 (A[2*i+1] + A[2*i+2]) % 10,并且如果 A[2*i+1] + A[2*i+2] >= 10,在替换消去时就可以得到 1 分,反之不得分。对于长度为 2^k 的序列,经过合并操作,每相邻的两个数依次消去替换,即可得到长度为 2^(k-1) 的序列,并得到相应分数。所以长度为 2^k 的序列在经过 k 轮消去后,最后会得到一个数,你需要计算消去过程中的总得分。

现给定一个长度为 N 的序列,有 Q 次独立的查询,每次查询代表对一个子序列(查询的子序列长度一定为 2 的幂次)进行消去替换,直至一个数为止,请计算该子序列的消除过程中总得分。

例如对[1,2,6,7,8,9] 的子序列 [6,7,8,9] 进行消去替换,第 1 轮后得到 [(6+7)%10, (8+9)%10)] = [3, 7],同时得分为 2;第 2 轮替换后得到 [(3+7)%10] = [0],同时得分为 1;总得分为 3。




输入描述:

输入数据包括Q + 3行。第1行包括一个数,N,代表输入序列长度;第2行依次为N个数,代表输入序列;第3行包括一个数,代表查询次数;接下来的Q行,每行包括2个数L_i,R_i,分别代表子序列的左端点和右端点。输入数据保证 1 <= N, Q <= 100000,且每次查询的子序列的长度,都是 2 的幂次。





输出描述:

输出数据:

输出数据包括Q行。每行为一个数,依次代表每一次查询的结果。

示例1

输入

6
1 2 3 4 5 6
3
1 2
1 4
3 6

输出

0
1
1

这道题你会答吗?花几分钟告诉大家答案吧!