{"problem":{"name":"[蓝桥杯 2022 国 A] 三角序列","description":{"content":"给定 $n$ 组成对的数 $a_i, b_i$，每组数表示一个 $a_i$ 行 $a_i$ 列的如图所示的三角形： ![](https://cdn.luogu.com.cn/upload/image_hosting/hp3n8ozb.png) 其中 $b_i$ 为 $0$ 时左边较低，为 $1$ 时右边较低。 将每组数对应的三角按数的顺序从左到右拼接起来。 现给出 $m$ 组询问 $l_i","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8797"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 组成对的数 $a_i, b_i$，每组数表示一个 $a_i$ 行 $a_i$ 列的如图所示的三角形：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/hp3n8ozb.png)\n\n其中 $b_i$ 为 $0$ 时左边较低，为 $1$ 时右边较低。\n\n将每组数对应的三角按数的顺序从左到右拼接起来。\n\n现给出 $m$ 组询问 $l_i, r_i, v_i$，对每组询问求最低高度 $h_i$ 使得 $l_i$ 到 $r_i$ 列之间的高度在 $h_i$ 以内的 $o$ 的数量大于等于 $v_i$。\n\n## Input\n\n输入的第一行包含两个整数 $n, m$，用一个空格分隔。\n\n接下来 $n$ 行，每行包含两个整数 $a_i, b_i$，用一个空格分隔。\n\n接下来 $m$ 行，每行包含三个整数 $l_i,r_i,v_i$，相邻两个整数之间用一个空格分隔。\n\n## Output\n\n输出一行包含一个字符串表示答案。\n\n[samples]\n\n## Background\n\n感谢 [Lotuses](https://www.luogu.com.cn/user/414231) 提供的数据\n\n## Note\n\n**【样例说明】**\n\n第一个询问对应的范围如图所示\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/iu9yky3i.png)\n\n**【评测用例规模与约定】**\n\n- 对于 $30\\%$ 的评测用例，$1 \\leq n, m, a_i \\leq 500$；\n- 对于 $50\\%$ 的评测用例，$1 \\leq n, m, a_i \\leq 5000$；\n- 对于所有评测用例，$1 \\leq n, m \\leq 2\\times10^5$，$1 \\leq a_i \\leq 10^6$，$0 \\leq b_i \\leq 1$，$1 \\leq l_i \\leq r_i \\leq \\sum a_i$，$1 \\leq v_i \\leq 10^{18}$。\n\n蓝桥杯 2022 国赛 A 组 I 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8797","tags":["莫队","线段树","二分","2022","可持久化线段树","分块","蓝桥杯国赛"],"sample_group":[["6 6\n3 0\n4 0\n2 1\n3 1\n5 0\n1 1\n3 9 12\n3 9 13\n3 4 4\n14 16 7\n9 15 12\n1 18 42","2\n3\n3\n3\n3\n-1"]],"created_at":"2026-03-03 11:09:25"}}