[ROIR 2023] 石头 (Day 2)

Luogu

IDLGP10100

Time1000ms

Memory512MB

DifficultyP5

2023ROIR（俄罗斯）

Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。 Bob 按照以下步骤进行 $n$ 次操作： - 在第一步，选择任意的 $i$（$1\le i\le n$），并将第 $i$ 个石头涂成白色。 - 在第 $2$ 到第 $n$ 步，选取相邻石头中至少有一个白色石头的黑色石头中的 $a_i$ 最小的石头 $j$（即，可能有很多个黑色石头满足它的相邻石头中至少有一个白色石头，但是要选取其中 $a_i$ 最小的那个），并将其涂成白色。很容易看出，在执行完所有步骤后，$n$ 个石头都是白色的。 Alice 选择了 $q$ 对值 $p_j$ 和 $k_j$。对于每对 $p$ 和 $k$ 的值，她想知道有多少种不同的选择第一步时将哪块石头涂成白色的方式，使得第 $p$ 块石头在第 $k$ 步变成白色。帮助 Bob 回答 Alice 的 $q$ 个查询。 ## Input 第一行包含两个整数 $n$ 和 $q$，分别表示石头的数量和查询的数量。第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示写在石头上的整数。接下来的 $q$ 行，每行包含一对整数 $p_j$ 和 $k_j$。 ## Output 对于每个查询，输出一个整数，表示查询的答案。 [samples] ## Background 翻译自 [ROIR 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。 ## Note 下面的样例解释中加粗的数是被涂成白色的。在第一个样例中： - 如果第一步选择第 $1$ 块石头： - 第 $1$ 步：$[\bold1, \gray4, \gray6, \gray5, \gray2, \gray3]$； - 第 $2$ 步：$[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$； - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$； - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $2$ 块石头： - 第 $1$ 步：$[\gray1, \bold4, \gray6, \gray5, \gray2, \gray3]$； - 第 $2$ 步：$[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$； - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$； - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $3$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \bold6, \gray5, \gray2, \gray3]$； - 第 $2$ 步：$[\gray1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$； - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $4$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \gray6, \bold5, \gray2, \gray3]$； - 第 $2$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \gray3]$； - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$； - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$； - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $5$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \gray3]$； - 第 $2$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$； - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$； - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$； - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $6$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \gray6, \gray5, \gray2, \bold3]$； - 第 $2$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$； - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$； - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$； - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。本题使用捆绑测试。 | 子任务编号 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $20$ | $n,q\le300$ | | $2$ | $17$ | $n\le3000$ | | $3$ | $12$ | $n\le50000,q\le10$ | | $4$ | $6$ | $a_i$ 的值递增 | | $5$ | $16$ | 所有 $k_i$ 相等 | | $6$ | $15$ | 所有 $p_i$ 相等 | | $7$ | $14$ | 无特殊性质 | 对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le q \le 10^5$，$1 \le a_i \le n$ 且所有 $a_i$ 互不相同，$1 \le p_j,k_j \le n$。

Samples

Input #1

6 4
1 4 6 5 2 3
3 1
2 2
6 3
4 3

Output #1

Input #2

Output #2

0
1
1

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2023] 石头 (Day 2)",
    "description": {
      "content": "Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。 Bob 按照以下步骤进行 $n$ 次操作： - 在第一步，选择任意的 $i$（$1\\le i\\le n$），并将第 $i$ 个石头涂成",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10100"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。\n\nBob 按照以下步骤进行 $n$ 次操作：\n\n- 在第一步，选择任意的 $i$（$1\\le i\\le n$），并将第 $i$ 个石头涂成...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments