[CCO 2022] Alternating Heights

Luogu

IDLGP10050

Time2000ms

Memory1000MB

DifficultyP4

二分2022CCO（加拿大）深度优先搜索 DFS图论建模拓扑排序双指针 two-pointer

Troy 计划给 CCO 的学生拍一张合影，他向你寻求帮助。有 $K$ 个学生，编号从 $1$ 到 $K$。Troy 忘记了学生的身高，但他记得没有两个学生的身高相同。 Troy 有一个序列 $A_{1}, A_{2}, \ldots, A_{N}$，表示合影中从左到右的学生顺序。一个学生可能在 $A$ 中出现多次。你不确定这张合影会怎么拍，但你不愿意认为 Troy 犯了错误。 Troy 会给你 $Q$ 个形式为 $x,y$ 的询问，每个询问为「给定学生序列 $A_{x}, A_{x+1}, \ldots, A_{y}$，他们的身高能否形成一个交替序列？」更具体地说，我们用 $h_i$ 表示第 $i$ 个学生的身高。如果存在一种身高分配$ h_1, h_2, \ldots, h_K$，使得 $h_{A_{x}}>h_{A_{x+1}}<h_{A_{x+2}}>h_{A_{x+3}}<\ldots h_{A_{y}}$，回答 `YES`；否则回答 `NO`。注意，每个查询都是独立的：也就是说，询问 $i$ 的身高分配与询问 $j$ 的身高分配无关 $(i\neq j)$。 ## Input 第一行包含三个用空格分隔的整数 $N, K$ 和 $Q$。第二行包含 $N$ 个整数，表示 $A_{1}, A_{2}, \ldots, A_{N}\left(1 \leq A_{i} \leq K\right)$。接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $x$ 和 $y (1 \leq x<y \leq N)$，表示一组查询。 ## Output 输出 $Q$ 行。第 $i$ 行，输出 `YES` 或者 `NO`，表示 Troy 的第 $i$ 个查询的答案。 [samples] ## Note ## 样例说明对于第一个询问，不可能有 $h_1>h_1$，所以答案是 `NO`。对于第二个询问，$h_1>h_2<h_3>h_1$ 的一种方案是 $h_1=160 \mathrm{~cm}, h_2=140 \mathrm{~cm}, h_3=180 \mathrm{~cm}$。另一种方案是 $h_1=1.55 \mathrm{~m}, h_2=1.473 \mathrm{~m}, h_3=1.81 \mathrm{~m}$。对于第三个询问，不可能同时有 $h_1>h_2$ 和 $h_1<h_2$。 ## 数据范围对于所有的数据，有 $2 \leq N \leq 3000$，$2 \leq K \leq N$，$1 \leq Q \leq 10^{6}$。子任务编号| 分值| $N$| $K$| $Q$ :-:|:-:|:-:|:-:|:-: $1$| $16$| $2 \leq N \leq 3000$| $K=2$| $1 \leq Q \leq 10^{6}$ $2$| $24$| $2 \leq N \leq 500$| $2 \leq K \leq \min (N, 5)$|$1 \leq Q \leq 10^{6}$ $3$ |$28$| $2 \leq N \leq 3000$ |$2 \leq K \leq N$ |$1 \leq Q \leq 2000$ $4$| $32$| $2 \leq N \leq 3000$ |$2 \leq K \leq N$ | $1 \leq Q \leq 10^{6}$

Samples

Input #1

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

Output #1

NO
YES
NO

API Response (JSON)

{
  "problem": {
    "name": "[CCO 2022] Alternating Heights",
    "description": {
      "content": "Troy 计划给 CCO 的学生拍一张合影，他向你寻求帮助。 有 $K$ 个学生，编号从 $1$ 到 $K$。Troy 忘记了学生的身高，但他记得没有两个学生的身高相同。 Troy 有一个序列 $A_{1}, A_{2}, \\ldots, A_{N}$，表示合影中从左到右的学生顺序。一个学生可能在 $A$ 中出现多次。你不确定这张合影会怎么拍，但你不愿意认为 Troy 犯了错误。 Troy ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1024000
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10050"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Troy 计划给 CCO 的学生拍一张合影，他向你寻求帮助。\n\n有 $K$ 个学生，编号从 $1$ 到 $K$。Troy 忘记了学生的身高，但他记得没有两个学生的身高相同。\n\nTroy 有一个序列 $A_{1}, A_{2}, \\ldots, A_{N}$，表示合影中从左到右的学生顺序。一个学生可能在 $A$ 中出现多次。你不确定这张合影会怎么拍，但你不愿意认为 Troy 犯了错误。\n\nTroy ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments