[CoE R5] 暴龙的白菜

Luogu

IDLGP8577

Time1000ms

Memory128MB

DifficultyP2

模拟洛谷原创O2优化前缀和洛谷月赛

给定一个字符串，由 $1$ 个 $\texttt{1}$，$2$ 个 $\texttt{2}$，$3$ 个 $\texttt{3}$，$4$ 个 $\texttt{4}$，$5$ 个 $\texttt{5}$，$6$ 个 $\texttt{6}$，$7$ 个 $\texttt{7}$，$8$ 个 $\texttt{8}$，$9$ 个 $\texttt{9}$，$10$ 个 $\texttt{10}$……以此类推，依次拼接而成。询问字符串第 $l$ 位到第 $r$ 位的数字之和。 ## Input **输入包含多组测试数据。** 第一行一个正整数 $T$。接下来 $T$ 组问询，每次两个正整数 $l,r$。 ## Output $T$ 行，每行一个整数代表答案。 [samples] ## Background 暴龙爱吃白菜。 ## Note **样例解释** 字符串为： $$\texttt{12233344445555566666677777778888888899999999910101010101010101010}\cdots\cdots$$ 对于第一组询问，第 $5$ 位到第 $9$ 位的数字之和为 $3+3+4+4+4=18$。对于第二组询问，第 $46$ 位到第 $50$ 位的数字之和为 $1 + 0 + 1 + 0 + 1 = 3$。 ------------ **数据范围** **本题采用捆绑测试。** - $\texttt{Subtask 1(10 pts)：}T=1$，$1\le l\le r\le 10$； - $\texttt{Subtask 2(20 pts)：}1\le T\le 10$，$1\le l\le r\le 10^3$； - $\texttt{Subtask 3(30 pts)：}1\le T\le 10^3$，$1\le l\le r\le 10^5$； - $\texttt{Subtask 4(40 pts)：}$无特殊限制。对于 $100\%$ 的数据，满足 $1\le T\le 10^5$，$1\le l\le r\le 10^6$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[CoE R5] 暴龙的白菜",
    "description": {
      "content": "给定一个字符串，由 $1$ 个 $\\texttt{1}$，$2$ 个 $\\texttt{2}$，$3$ 个 $\\texttt{3}$，$4$ 个 $\\texttt{4}$，$5$ 个 $\\texttt{5}$，$6$ 个 $\\texttt{6}$，$7$ 个 $\\texttt{7}$，$8$ 个 $\\texttt{8}$，$9$ 个 $\\texttt{9}$，$10$ 个 $\\texttt{10}",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8577"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个字符串，由 $1$ 个 $\\texttt{1}$，$2$ 个 $\\texttt{2}$，$3$ 个 $\\texttt{3}$，$4$ 个 $\\texttt{4}$，$5$ 个 $\\texttt{5}$，$6$ 个 $\\texttt{6}$，$7$ 个 $\\texttt{7}$，$8$ 个 $\\texttt{8}$，$9$ 个 $\\texttt{9}$，$10$ 个 $\\texttt{10}...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments