[蓝桥杯 2022 国 A] 三角序列

Luogu

IDLGP8797

Time3000ms

Memory512MB

DifficultyP5

莫队线段树二分2022可持久化线段树分块蓝桥杯国赛

给定 $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, r_i, v_i$，对每组询问求最低高度 $h_i$ 使得 $l_i$ 到 $r_i$ 列之间的高度在 $h_i$ 以内的 $o$ 的数量大于等于 $v_i$。 ## Input 输入的第一行包含两个整数 $n, m$，用一个空格分隔。接下来 $n$ 行，每行包含两个整数 $a_i, b_i$，用一个空格分隔。接下来 $m$ 行，每行包含三个整数 $l_i,r_i,v_i$，相邻两个整数之间用一个空格分隔。 ## Output 输出一行包含一个字符串表示答案。 [samples] ## Background 感谢 [Lotuses](https://www.luogu.com.cn/user/414231) 提供的数据 ## Note **【样例说明】** 第一个询问对应的范围如图所示 ![](https://cdn.luogu.com.cn/upload/image_hosting/iu9yky3i.png) **【评测用例规模与约定】** - 对于 $30\%$ 的评测用例，$1 \leq n, m, a_i \leq 500$； - 对于 $50\%$ 的评测用例，$1 \leq n, m, a_i \leq 5000$； - 对于所有评测用例，$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}$。蓝桥杯 2022 国赛 A 组 I 题。

Samples

Input #1

Output #1

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments