[THUPC 2024 决赛] 古明地枣的袜子

Luogu
IDLGP10540
Time10000ms
Memory1024MB
DifficultyP7
2024THUPC
你需要维护一个序列 $a_1,\dots,a_n$ 。 给定一个操作序列 $(x_1,y_1),\dots,(x_n,y_n)$ ,操作 $(x,y)$ 表示将 $a_1,\dots,a_x$ 的值加上 $y$ 。 共 $m$ 次查询,每次查询给出 $l,r$ ,问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\dots,(x_r,y_r)$ ,最后 $\max\limits_{i=1}^n a_i$ 的值。 ## Input 第一行两个整数 $n,m$ ($1\le n,m\le 5\times 10^5$); 接下来 $n$ 行每行两个整数 $x_i,y_i$($1\le x_i\le n, |y_i|\le n$); 接下来 $m$ 行,每行两个整数 $l,r$($1\le l\le r\le n$)。 ## Output 输出 $m$ 行,每行一个整数,表示每次查询的答案。 [samples] ## Note **来源与致谢** 来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)决赛。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>
Samples
Input #1
6 5
6 4
2 6
5 -5
3 6
1 2
3 6
1 6
1 6
2 6
2 6
5 6
Output #1
19
19
15
15
8
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2024 决赛] 古明地枣的袜子",
    "description": {
      "content": "你需要维护一个序列 $a_1,\\dots,a_n$ 。 给定一个操作序列 $(x_1,y_1),\\dots,(x_n,y_n)$ ,操作 $(x,y)$ 表示将 $a_1,\\dots,a_x$ 的值加上 $y$ 。 共 $m$ 次查询,每次查询给出 $l,r$ ,问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\\dots,(x_r,y_r)$ ,最后 $\\max\\li",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10540"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你需要维护一个序列 $a_1,\\dots,a_n$ 。\n\n给定一个操作序列 $(x_1,y_1),\\dots,(x_n,y_n)$ ,操作 $(x,y)$ 表示将 $a_1,\\dots,a_x$ 的值加上 $y$ 。\n\n共 $m$ 次查询,每次查询给出 $l,r$ ,问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\\dots,(x_r,y_r)$ ,最后 $\\max\\li...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments