Candies!

题意翻译

## 题目描述 考虑一个长度为 $2^k$ 的序列 $[a_1,a_2,...,a_{2^k}]\ (0 \leq a_i \leq 9)$ 。我们对这个序列进行下列操作： 每次选中 $(a_{2i+1},a_{2i}) (0\leq i < 2^{k-1})$ ，共$2^{k-1}$对数字，若$a_{2i+1}+a_{2i}\ge 10$，你就能获得一颗糖果！ ，之后将每一个$(a_{2i+1}+a_{2i}) \mod 10$ 按 $i$ 从小到大重新写成一排，形成一个新的序列，长度为$2^{k-1}$ 我们不断执行这个操作直到序列的长度变为 $1$ 。我们用$f[a_1,a_2,...,a_k]$表示我们对序列$[a_1,a_2,...,a_k]$不断进行操作，最终一共获得的糖果。 举个栗子：序列为$[8,7,3,1,7,0,9,4]$ 第一步之后序列变为$[5,4,7,3]$，因为$8+7\ge 10 ,9+4 \ge 10$ 所以获得 $2$ 颗糖果 第二步之后序列变为$[9,0]$，因为$7+4 \ge 10$ 所以获得 $1$ 颗糖果 第三步之后序列变为$[9]$ 所以 $f([8,7,3,1,7,0,9,4]) = 3$，因为我们一共得到 $3$ 颗糖果 所以现在你有一个长度为 $n$ 的序列 $s_1,s_2,...,s_n$ ，给你 $q$ 组询问，每一次询问一个长度为 $2$ 的整数次幂的区间 $[l_i,r_i]$，请输出 $f([s_{l_i},s_{l_{i+1}},...,s_{r_i}])$ ## 输入输出格式 ### 输入格式： 第一行为一个整数 $n(1\leq n \leq 10^5)$，表示序列的长度 第二行为长度为 $n$ 的序列 $s[1...n] ,(0\leq s_i \leq 9)$ 第三行为一个整数 $q(1\leq q \leq 10^5)$ 表示询问个数 此后 $q$ 行每一行为两个整数 $l_i,r_i$，表示第 $i$ 个询问。保证 $r_i - l_i + 1$ 是 $2$ 的整数次幂 ### 输出格式： 总共 $q$ 行，第 $i$ 行为第 $i$ 个询问的结果 ## 说明 样例一就是题目描述中的例子 $f([7,3,1,7])=1$，因为 $[7,3,1,7] \rightarrow [0,8] \rightarrow [8]$ ，其中$7 + 3 \ge 10$ 所以只获得 $1$ 个糖果 $f([9])=0$，因为我们不需要进行操作。

题目描述

Consider a sequence of digits of length $ 2^k $ $ [a_1, a_2, \ldots, a_{2^k}] $ . We perform the following operation with it: replace pairs $ (a_{2i+1}, a_{2i+2}) $ with $ (a_{2i+1} + a_{2i+2})\bmod 10 $ for $ 0\le i<2^{k-1} $ . For every $ i $ where $ a_{2i+1} + a_{2i+2}\ge 10 $ we get a candy! As a result, we will get a sequence of length $ 2^{k-1} $ . Less formally, we partition sequence of length $ 2^k $ into $ 2^{k-1} $ pairs, each consisting of 2 numbers: the first pair consists of the first and second numbers, the second of the third and fourth $ \ldots $ , the last pair consists of the ( $ 2^k-1 $ )-th and ( $ 2^k $ )-th numbers. For every pair such that sum of numbers in it is at least $ 10 $ , we get a candy. After that, we replace every pair of numbers with a remainder of the division of their sum by $ 10 $ (and don't change the order of the numbers). Perform this operation with a resulting array until it becomes of length $ 1 $ . Let $ f([a_1, a_2, \ldots, a_{2^k}]) $ denote the number of candies we get in this process. For example: if the starting sequence is $ [8, 7, 3, 1, 7, 0, 9, 4] $ then: After the first operation the sequence becomes $ [(8 + 7)\bmod 10, (3 + 1)\bmod 10, (7 + 0)\bmod 10, (9 + 4)\bmod 10] $ $ = $ $ [5, 4, 7, 3] $ , and we get $ 2 $ candies as $ 8 + 7 \ge 10 $ and $ 9 + 4 \ge 10 $ . After the second operation the sequence becomes $ [(5 + 4)\bmod 10, (7 + 3)\bmod 10] $ $ = $ $ [9, 0] $ , and we get one more candy as $ 7 + 3 \ge 10 $ . After the final operation sequence becomes $ [(9 + 0) \bmod 10] $ $ = $ $ [9] $ . Therefore, $ f([8, 7, 3, 1, 7, 0, 9, 4]) = 3 $ as we got $ 3 $ candies in total. You are given a sequence of digits of length $ n $ $ s_1, s_2, \ldots s_n $ . You have to answer $ q $ queries of the form $ (l_i, r_i) $ , where for $ i $ -th query you have to output $ f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}]) $ . It is guaranteed that $ r_i-l_i+1 $ is of form $ 2^k $ for some nonnegative integer $ k $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the sequence. The second line contains $ n $ digits $ s_1, s_2, \ldots, s_n $ ( $ 0 \le s_i \le 9 $ ). The third line contains a single integer $ q $ ( $ 1 \le q \le 10^5 $ ) — the number of queries. Each of the next $ q $ lines contains two integers $ l_i $ , $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — $ i $ -th query. It is guaranteed that $ r_i-l_i+1 $ is a nonnegative integer power of $ 2 $ .

输出格式

Output $ q $ lines, in $ i $ -th line output single integer — $ f([s_{l_i}, s_{l_i + 1}, \ldots, s_{r_i}]) $ , answer to the $ i $ -th query.

输入输出样例

输入样例 #1

8
8 7 3 1 7 0 9 4
3
1 8
2 5
7 7

输出样例 #1

3
1
0

输入样例 #2

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

输出样例 #2

0
0
1

说明

The first example illustrates an example from the statement. $ f([7, 3, 1, 7]) = 1 $ : sequence of operations is $ [7, 3, 1, 7] \to [(7 + 3)\bmod 10, (1 + 7)\bmod 10] $ $ = $ $ [0, 8] $ and one candy as $ 7 + 3 \ge 10 $ $ \to $ $ [(0 + 8) \bmod 10] $ $ = $ $ [8] $ , so we get only $ 1 $ candy. $ f([9]) = 0 $ as we don't perform operations with it.