打卡信奥刷题（3402）用C++实现信奥题 P10050 [CCO 2022] Alternating Heights

rogeliu

243人浏览 · 2026-06-23 07:11:58

rogeliu · 2026-06-23 07:11:58 发布

P10050 [CCO 2022] Alternating Heights

题目描述

Troy 计划给 CCO 的学生拍一张合影，他向你寻求帮助。

有 $K$ 个学生，编号从 $1$ 到 $K$ 。Troy 忘记了学生的身高，但他记得没有两个学生的身高相同。

Troy 有一个序列 $A1,A2,…,ANA_{1}, A_{2}, \ldots, A_{N}$ ，表示合影中从左到右的学生顺序。一个学生可能在 $A$ 中出现多次。你不确定这张合影会怎么拍，但你不愿意认为 Troy 犯了错误。

Troy 会给你 $Q$ 个形式为 $x, y$ 的询问，每个询问为「给定学生序列 $Ax,Ax+1,…,AyA_{x}, A_{x+1}, \ldots, A_{y}$ ，他们的身高能否形成一个交替序列？」更具体地说，我们用 $h_i$ 表示第 $i$ 个学生的身高。如果存在一种身高分配$ h_1, h_2, \ldots, h_K$，使得 $hAx>hAx+1<hAx+2>hAx+3<…hAyh_{A_{x}}>h_{A_{x+1}}<h_{A_{x+2}}>h_{A_{x+3}}<\ldots h_{A_{y}}$ ，回答 YES；否则回答 NO。

注意，每个查询都是独立的：也就是说，询问 $i$ 的身高分配与询问 $j$ 的身高分配无关 $(i≠j)(i\neq j)$ 。

输入格式

第一行包含三个用空格分隔的整数 $N, K$ 和 $Q$ 。

第二行包含 $N$ 个整数，表示 $A1,A2,…,AN(1≤Ai≤K)A_{1}, A_{2}, \ldots, A_{N}\left(1 \leq A_{i} \leq K\right)$ 。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $x$ 和 $\leq x<y \leq N)$ ，表示一组查询。

输出格式

输出 $Q$ 行。第 $i$ 行，输出 YES 或者 NO，表示 Troy 的第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

NO
YES
NO

说明/提示

样例说明

对于第一个询问，不可能有 $h_1>h_1$ ，所以答案是 NO。

对于第二个询问， $h_1>h_2<h_3>h_1$ 的一种方案是 $cmh_1=160 \mathrm{~cm}, h_2=140 \mathrm{~cm}, h_3=180 \mathrm{~cm}$ 。另一种方案是 $mh_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$ 。

数据范围

对于所有的数据，有 $\leq N \leq 3000$ ， $\leq K \leq N$ ， $\leq Q \leq 10^{6}$ 。

子任务编号	分值	$N$	$K$	$Q$
$1$	$16$	$\leq N \leq 3000$	$K = 2$	$\leq Q \leq 10^{6}$
$2$	$24$	$\leq N \leq 500$	$\leq K \leq \min (N, 5)$	$\leq Q \leq 10^{6}$
$3$	$28$	$\leq N \leq 3000$	$\leq K \leq N$	$\leq Q \leq 2000$
$4$	$32$	$\leq N \leq 3000$	$\leq K \leq N$	$\leq Q \leq 10^{6}$

C++实现

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 3005;
int n, k, q;
int a[N], wzj[N],ind[N];
vector<int> g[N];
queue<int> que;
inline bool lwhzkj(int l, int r) {
    for(int i = 1; i <= n; i++) g[i].clear();
    for(int i = l; i < r; i++) {
        if(i % 2 == 0) g[a[i]].push_back(a[i + 1]), ind[a[i + 1]]++;
        else g[a[i + 1]].push_back(a[i]), ind[a[i]]++;
    }
    for(int i = 1; i <= n; i++) {
        if(!ind[i]) que.push(i);
    }
    int u, v;
    while(!que.empty()) {
        u = que.front(), que.pop();
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i], ind[v]--;
            if(!ind[v]) que.push(v);
        }
    }
    u = 0;
    for(int i = 1; i <= n; i++) u += min(1, ind[i]), ind[i] = 0;
    return u == 0;
}
int main() {
    scanf("%d%d%d", &n, &k, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int l, r, mid;
    for(int li = 1; li <= n; li++) {
        l = li, r = n + 1;
        while(l + 1 < r) {
            mid = (l + r) >> 1;
            if(lwhzkj(li, mid)) l = mid;
            else r = mid;
        }
        wzj[li] = l;
    }
    for(int i = 1; i <= q; i++) scanf("%d%d", &l, &r), puts((wzj[l] >= r) ? "YES" : "NO");
    return 0;
}