[蓝桥杯 2014 国 B] Log 大侠

Luogu
IDLGP8618
Time1000ms
Memory128MB
DifficultyP4
2014蓝桥杯国赛
atm 参加了速算训练班,经过刻苦修炼,对以 $2$ 为底的对数算得飞快,人称 Log 大侠。 一天,Log 大侠的好友 drd 有一些整数序列需要变换,Log 大侠正好施展法力。 变换的规则是:对其某个子序列的每个整数变为 $[\log_2(x)+1]$ 其中 [] 表示向下取整,就是对每个数字求以 $2$ 为底的对数,然后取下整。 例如对序列 $3,4,2$ 操作一次后,这个序列会变成 $2,3,2$。 drd 需要知道,每次这样操作后,序列的和是多少。 ## Input 第一行两个正整数 $n,m$。 第二行 $n$ 个数,表示整数序列,都是正数。 接下来 $m$ 行,每行两个数 $L$,$R$ 表示 atm 这次操作的是区间 $[L,R]$,数列序号从 $1$ 开始。 ## Output 输出 $m$ 行,依次表示 atm 每做完一个操作后,整个序列的和。 [samples] ## Note 对于 $30\%$ 的数据,$n,m \le 10^3$。 对于 $100\%$ 的数据,$n,m \le 10^5$。 时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛 官方数据似乎有错。重造数据按照 $1 \leq a_i \leq 10^9$ 设计。
Samples
Input #1
3 3
5 6 4
1 2
2 3
1 3
Output #1
10
8
6
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2014 国 B] Log 大侠",
    "description": {
      "content": "atm 参加了速算训练班,经过刻苦修炼,对以 $2$ 为底的对数算得飞快,人称 Log 大侠。 一天,Log 大侠的好友 drd 有一些整数序列需要变换,Log 大侠正好施展法力。 变换的规则是:对其某个子序列的每个整数变为 $[\\log_2(x)+1]$ 其中 [] 表示向下取整,就是对每个数字求以 $2$ 为底的对数,然后取下整。 例如对序列 $3,4,2$ 操作一次后,这个序列会变成 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8618"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "atm 参加了速算训练班,经过刻苦修炼,对以 $2$ 为底的对数算得飞快,人称 Log 大侠。\n\n一天,Log 大侠的好友 drd 有一些整数序列需要变换,Log 大侠正好施展法力。\n\n变换的规则是:对其某个子序列的每个整数变为 $[\\log_2(x)+1]$ 其中 [] 表示向下取整,就是对每个数字求以 $2$ 为底的对数,然后取下整。\n\n例如对序列 $3,4,2$ 操作一次后,这个序列会变成 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments