{"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\\limits_{i=1}^n a_i$ 的值。\n\n## Input\n\n第一行两个整数 $n,m$ （$1\\le n,m\\le 5\\times 10^5$）；\n\n接下来 $n$ 行每行两个整数 $x_i,y_i$（$1\\le x_i\\le n, |y_i|\\le n$）；\n\n接下来 $m$ 行，每行两个整数 $l,r$（$1\\le l\\le r\\le n$）。\n\n## Output\n\n输出 $m$ 行，每行一个整数，表示每次查询的答案。\n\n[samples]\n\n## Note\n\n**来源与致谢**\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。\n\n数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10540","tags":["2024","THUPC"],"sample_group":[["6 5\n6 4\n2 6\n5 -5\n3 6\n1 2\n3 6\n1 6\n1 6\n2 6\n2 6\n5 6\n","19\n19\n15\n15\n8\n"]],"created_at":"2026-03-03 11:09:25"}}