题解：Alternating Heights

题目分析

问题核心

给定包含重复学生编号的序列 (A) 和多个查询 ([x,y])，判断是否存在学生身高分配（所有身高互不相同），使得子序列 (A_x, A_{x+1}, ..., A_y) 满足交替大小关系：(h_{A_x} > h_{A_{x+1}} < h_{A_{x+2}} > h_{A_{x+3}} < ...)（或起始为小于的对称情况，本质等价）。

关键观察

1. 交替序列的相邻元素约束可转化为有向边：
   • 若位置 (i)（相对于查询子序列的偏移）为奇数（1-based），需满足 (h_{A_{x+i-1}} > h_{A_{x+i}})，对应有向边 (A_{x+i-1} \rightarrow A_{x+i})（表示前者身高大于后者）；
   • 若位置 (i) 为偶数，需满足 (h_{A_{x+i-1}} < h_{A_{x+i}})，对应有向边 (A_{x+i} \rightarrow A_{x+i-1})（表示后者身高大于前者）。
2. 身高分配存在的充要条件：上述有向图无环（DAG）。因为无环图可通过拓扑排序分配身高（拓扑序中靠前的节点身高更小），且所有身高互不相同。

数据范围挑战

• (N \leq 3000)，(Q \leq 10^6)。若直接对每个查询构建图并判断环，时间复杂度为 (O(Q \cdot (N+K)))，会超时。
• 需预处理每个左端点 (l) 对应的最大右端点 (R[l])，使得 ([l, R[l]]) 是合法子序列，查询时直接判断 (y \leq R[l]) 即可。

算法设计

预处理阶段（核心）

1. 双指针枚举左端点 (l)：固定左端点 (l)，用右指针 (r) 从 (l) 开始向右扩展，维护当前子序列 ([l, r]) 对应的有向图。
2. 动态维护有向图与拓扑排序：
   • 扩展 (r) 时，根据 (r-l) 的奇偶性（确定约束类型），添加 (A[r]) 与 (A[r+1]) 之间的有向边。
   • 用拓扑排序判断当前图是否无环：若有环，说明 (r) 已超出 (l) 对应的最大合法右端点，记录 (R[l] = r-1)，并移动左端点 (l)；若无环，继续扩展 (r)。
3. 记录最大合法右端点：对于每个 (l)，(R[l]) 表示以 (l) 为起点的最长合法子序列的右端点。

查询阶段

• 对于每个查询 ([x,y])，直接判断 (y \leq R[x])：若是则输出 YES，否则输出 NO。查询时间复杂度为 (O(1))，可处理 (10^6) 个查询。

代码关键模块解析

1. 图结构与拓扑排序

struct CFS {
    int tot, h[N], deg[N];
    struct edge { int v, nxt; };
    edge e[N];
    void Init(int n) { /* 初始化邻接表和入度数组 */ }
    void att(int u, int v) { /* 添加有向边 u->v，更新入度 */ }
} g;

bool Check(int l, int r) {
    g.Init(m);
    // 构建 [l, r] 对应的有向图
    FOR(i, l, r-1) 
        if (!((i ^ l) & 1)) g.att(a[i], a[i+1]); // 奇数位置（相对l）：a[i] > a[i+1]
        else g.att(a[i+1], a[i]); // 偶数位置：a[i] < a[i+1]
    // 拓扑排序判断是否无环
    queue<int> q;
    int cnt = 0;
    FOR(i, 1, m) if (!g.deg[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt++;
        // 遍历邻接边，更新入度
        for (int i = g.h[u]; ~i; i = g.e[i].nxt) {
            int v = g.e[i].v;
            if (--g.deg[v] == 0) q.push(v);
        }
    }
    return cnt == m; // 所有节点都被访问，说明无环
}

• Check(l, r) 函数：构建子序列 ([l, r]) 对应的有向图，通过拓扑排序判断是否无环。若返回 true，说明该子序列合法。

2. 双指针预处理 (R[l])

int l = 1, r = 1;
while (l <= r && r <= n) {
    if (Check(l, r)) r++; // 无环，扩展右指针
    else {
        R[l] = r - 1; // 有环，记录最大合法右端点
        l++; // 移动左指针
        r = max(r, l); // 确保 r 不小于 l
    }
}
// 处理剩余的 l（从 l 到 n 均合法）
FOR(i, l, n) R[i] = n;

• 双指针遍历：左指针 (l) 从 1 到 (n)，右指针 (r) 尽可能向右扩展，确保每个 (l) 对应的 (R[l]) 是最大合法右端点。

3. 快速查询处理

while (Q--) {
    int l, r;
    I(l, r);
    puts(r <= R[l] ? "YES" : "NO");
}

• 利用预处理的 (R) 数组，每个查询仅需 (O(1)) 判断。

时间复杂度分析

• 预处理阶段：双指针遍历中，每个右指针 (r) 最多移动 (N) 次，每次 Check 函数的拓扑排序复杂度为 (O(K + E))（(E) 为边数，最多 (N)）。总预处理复杂度为 (O(N \cdot (K + N)))，因 (N \leq 3000)，计算量约为 (3000 \times (3000 + 3000) = 1.8 \times 10^7)，可接受。
• 查询阶段：(O(Q))，可处理 (10^6) 个查询。

空间复杂度分析

• 图结构存储：邻接表和入度数组均为 (O(K + N))，符合 (N \leq 3000) 的空间限制。