Escape Through the Leaf（迫真）

sim_sugar · 2023-05-22 21:49:53 · 个人记录

Sub1：C-B。
Sub2 / 3 / 4：考虑 i \to lef_i,rig_i 连边，每次对 S \in [A,B] 的点 dis 设为 0，BFS 即可，O(nq)。
Sub5：首先如果 (A,C) 存在 h_x \gt h_C 那么一定无解。考虑一个贪心策略：每次在 i 向高度比 h_C 更低的、高度更高的那一边跳，这个显然是对的（在点 i 考虑左右两个单调序列），问题是如何满足比 h_C 更低。注意到，如果在 i 无法向左跳，那么在之后跳到的点也一定无法向左跳，故之后一直向右跳，这部分的答案很容易用单调栈预处理。于是问题变为找出这样贪心跳的过程中第一个 h_{lef} \gt h_C 的点 x，并且求只保留 i \to \max(lef,rig) 的边，i \to x 的距离，注意到这样连边每个点有且只有一条出边，所以连成一个森林，~~那么距离是容易预处理的~~ 那么可以倍增跳求距离。对于找 x，就是在祖先链上找到最深的 h_{lef} \gt h_c 的点，这个也是可以倍增做到 O(q \log n) 的。
Sub6：正着做就会有 O(n) 个 x，所以只能倒着做（，连边变为 i \to \min(lef,rig)，并且这里如果 i 能一步跳到 y \in [l,r] 那么就不会贪心地往另一边更低的走，那找终点 x 就会变成祖先链上最深的满足 h_{rig} \lt \min_{i=A}^{B} h_i 或 lef \in [A,B] 的点（注意 rig \in [A,B] 是不可能作为最后一步的起点的），你可以树剖之后对每条重链建动态开点线段树，维护的是区间 \max dep 以及对应的编号，那么这个也是可以 O(q \log n) 的，同理上面那个 Subtask 的倍增也是可以换成树剖 + 线段树二分的。

但是这两个 Subtask 的做法都强依赖于固定了一边的端点（

所以虽然貌似有 81 pts 了但是好像跟正解没什么关系（

草（，关系很大。

起点一定是 \max([A,B])（这里 A 是修正后的左端点，即极小的满足 h_A \lt \max([C,D]) 的 A）（其实这是十分显然的，~~不知道为什么有人看不出来~~）。

所以倒过来使用 Sub6 的做法就做完了。于是你有了一个时间 O(q \log n) 空间 O(n \log n) 的 neuze 做法，~~感觉不是很好写~~ 好写阿，很好写阿。

事实上你 Sub6 的做法也可以倍增 /yun

这里就考虑从 \max([A,B]) 正着跳到 [C,D] 里，考虑如果 rig_x \in [C,D] 那么 h_{rig_x} 满足什么条件，其实就是 h_{rig_x} \in (\max_{i=B}^{C-1} h_i , \max_{i=C}^{D} h_i]（因为一定有 \text{max of } [B,C-1] \le \text{max of } [C,D]），那么因为跳的过程中 h_{rig} 是递增的，我们先倍增地跳到这个区间里，然后判断是否合法，是就直接跳进去求出答案；否则再继续跳到 h_{lef} \gt \max([C,D]) 的那个祖先就行了。因为有 h 的单调性，你甚至不需要建出上文所说的森林（

找性质应该找全（

注意边界（nxt / rig[0 ~ 17][n+1]），WA 了一万发（

constexpr int Q = 200003, oo = 2e9;
int n, Log2[Q], a[Q], seq[Q];
__attribute__((constructor)) static void
___________(){ for(int i = 2; i < Q; ++i) Log2[i] = Log2[i>>1] + 1; }

template<int N> struct MaxList {
    static const int LOG = 31-__builtin_clz(N); int st[LOG+1][N];
    inline int MAX(int i, int j){ return a[i] > a[j] ? i : j; }
    inline void Make(int n, int *a){ copy(a+1, a+n+1, st[0]+1); for(int j = 1; j <= Log2[n]; ++j) for(int i = n-(1<<j-1); i >= 1; --i) st[j][i] = MAX(st[j-1][i], st[j-1][i+(1<<j-1)]); }
    inline int Max(int l, int r){ int K = Log2[r-l+1]; return MAX(st[K][l], st[K][r-(1<<K)+1]); }
}; MaxList<Q> st; int L[Q], R[Q], nxt[18][Q], rig[18][Q], sta[Q], top;

void init(int N, vector<int> H) {
    n = N; for(int i = 1; i <= n; ++i) seq[i] = i;
    copy(begin(H), end(H), a+1), st.Make(n, seq);
    sta[top = 1] = 0, a[0] = +oo;
    for(int i = 1; i <= n; sta[++top] = i, ++i)
        for(L[i] = sta[top]; a[sta[top]] <= a[i]; L[i] = sta[--top]);
    sta[top = 1] = n+1, a[n+1] = +oo;
    for(int i = n; i >= 1; sta[++top] = i, --i)
        for(R[i] = sta[top]; a[sta[top]] <= a[i]; R[i] = sta[--top]);
    for(int i = 1; i <= n; ++i)
        rig[0][i] = R[i], nxt[0][i] = a[L[i]] > a[R[i]] ? L[i] : R[i];
    rig[0][n+1] = nxt[0][n+1] = n+1;
    for(int j = 1; j < 18; ++j)
        for(int i = 1; i <= n+1; ++i)
            nxt[j][i] = nxt[j-1][nxt[j-1][i]], rig[j][i] = rig[j-1][rig[j-1][i]]; 
//  fprintf(stderr, "!!!! ");
//  for(int i = n; i >= 1; --i) fprintf(stderr, "(%d , %d)%c", R[i], dep[i], " \n"[i == 1]);
}
int minimum_jumps(int A, int B, int C, int D) {
//  fprintf(stderr, "sol [%d , %d] , [%d , %d]\n", A, B, C, D);
    ++A, ++B, ++C, ++D;
    int res = 0, ptr = 0, pos = st.Max(C, D);
    int Upd1 = a[st.Max(B, C-1)], Upd2 = a[pos];
    int l = A, r = B, mid, ans = B+1;
    while(l <= r) mid = l+r>>1, a[st.Max(mid, B)] < Upd2 ? (ans = mid, r = mid-1) : (l = mid+1);
    if(ans > B || Upd1 > Upd2) return -1; ptr = st.Max(ans, B);
    for(int j = 17; j >= 0; --j)
        if(a[nxt[j][ptr]] <= Upd1) res += 1<<j, ptr = nxt[j][ptr];
    if(ptr >= C && ptr <= D) return res; // 已经在区间内
    if(R[ptr] >= C && R[ptr] <= D) return res + 1; // 跳一步
    if(R[nxt[0][ptr]] >= C && R[nxt[0][ptr]] <= D) return res + 2; // 跳两步
    for(int j = 17; j >= 0; --j)
        if(rig[j][ptr] < C) res += 1<<j, ptr = rig[j][ptr]; // 跳祖先
    return res + 1;
}