题解：P16330 Just Because!

ssy666666 · 2026-10-20 19:57:57 · 题解

啊我竟然不知道这个经典问题可以倍增啊。

考虑这个问题，实际上，如果不存在两棵树往一边倒并且有交的情况，就相当于我们要选一堆无交的，价值为 1 的线段。这个的话可以倍增做。

那考虑两棵树往一边倒的情况。我们不妨把两棵树合并成一个价值为 2 的线段，然后做。

因此，我们设 r_{i,1/2} 表示左端点大于等于 i，选价值为 1 或 2，下一个能选的最左的左端点是哪个。

这个的话你线段树维护即可。从后往前扫一遍。

我们先考虑设 g_{i,j} 表示从左端点为 i 开始，选价值为 2^j 的线段，下一次选最左侧的左端点在哪里。

但是我们发现是难以转移的。因为我们完全有可能出现这种情况：

显然你朴素倍增这种情况就炸飞了。

我们不妨多定义一个 f_{i,j} 表示从左端点 i 开始，选价值为 2^j-1 的线段，这样就可以进行转移了。

然后算答案的话，你发现同样的问题，所以你需要记录走 x 步和走 x+1 步的答案，然后类似的进行转移即可。

AC Code

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 5e5 + 7 ;
const int MAXL = 22 ;
const int INF = 2e9 + 7 ;
int n , q ;
int p[MAXN] ;
int h[MAXN] ;
int nxt[MAXN] ;

struct SegmentTree {
    int tr[4 * MAXN] ;

    void BuildTree(int u , int l , int r) {
        tr[u] = n + 1 ;

        if (l == r) return ;

        int mid = (l + r) >> 1 ;
        BuildTree(u * 2 , l , mid) ;
        BuildTree(u * 2 + 1 , mid + 1 , r) ;
        return ;
    }

    void Change(int u , int l , int r , int dir , int val) {
        if (l == r) {
            tr[u] = min(val , tr[u]) ;
            return ;
        }

        int mid = (l + r) >> 1 ;
        if (mid >= dir) Change(u * 2 , l , mid , dir , val) ;
        else    Change(u * 2 + 1 , mid + 1 , r , dir , val) ;

        tr[u] = min(tr[u * 2] , tr[u * 2 + 1]) ;
    }

    int Query(int u , int l , int r , int gl , int gr) {
        if (gl > gr)    return n + 1 ;
        if (gl <= l and r <= gr)    return tr[u] ;

        int mid = (l + r) >> 1 ;
        int ans = n + 1 ;
        if (mid >= gl)  ans = min(ans , Query(u * 2 , l , mid , gl , gr)) ;
        if (mid + 1 <= gr)  ans = min(ans , Query(u * 2 + 1 , mid + 1 , r , gl , gr)) ;

        return ans ;
    }
}o ;

int ord[MAXN] ;

int r[MAXN][3] ;

int f[MAXL][MAXN] , g[MAXL][MAXN] ;
signed main() {
//  freopen("cut.in" , "r" , stdin) ;
//  freopen("cut.out" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    cin >> n >> q ;

    for (int i = 1 ; i <= n ; i ++) {
        cin >> p[i] ;
    }

    p[n + 1] = INF ;

    for (int i = 1 ; i <= n ; i ++) {
        cin >> h[i] ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        ord[i] = i ;
        nxt[i] = upper_bound(p + 1 , p + 1 + n , p[i] + h[i]) - p - 1 ;
    }

    sort (ord + 1 , ord + n + 1 , [](int i , int j) -> bool {
        return p[i] - h[i] > p[j] - h[j] ;
    }) ;

    int z = 1 ;
    r[n + 1][0] = r[n + 1][1] = r[n + 1][2] = n + 1 ;

    o.BuildTree(1 , 1 , n) ;
    for (int i = n ; i >= 1 ; i --) {
        while (z <= n and p[ord[z]] - h[ord[z]] > p[i]) {
            o.Change(1 , 1 , n , ord[z] , ord[z]) ;
            z ++ ;
        }

        r[i][2] = min(o.Query(1 , 1 , n , nxt[i] + 1 , n) + 1 , n + 1) ;
        r[i][2] = min(r[i + 1][2] , r[i][2]) ;

        while (z <= n and p[ord[z]] - h[ord[z]] > p[i - 1]) {
            o.Change(1 , 1 , n , ord[z] , ord[z]) ;
            z ++ ;
        }

        r[i][1] = min(o.Query(1 , 1 , n , i , n) + 1 , n + 1) ;
        r[i][1] = min(r[i][1] , r[i + 1][1]) ; 
    }

    for (int i = n ; i >= 1 ; i --) {
        r[i][1] = min(r[i][1] , (int)(upper_bound(p + 1 , p + 1 + n , p[i] + h[i]) - p)) ;
        r[i][1] = min(r[i][1] , r[i + 1][1]) ;

        r[i][2] = min(r[i][2] , r[r[i][1]][1]) ;
        r[i][2] = min(r[i][2] , r[i + 1][2]) ;
    }

    for (int i = 0 ; i < MAXL ; i ++) {
        for (int j = 1 ; j <= n + 1 ; j ++) {
            f[i][j] = g[i][j] = n + 1 ;
        }
    }

    for (int i = 1 ; i <= n ; i ++) {
        f[1][i] = r[i][1] ;
        g[1][i] = r[i][2] ;
    }

    for (int i = 2 ; i < MAXL ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            f[i][j] = min(g[i - 1][f[i - 1][j]] , f[i - 1][g[i - 1][j]]) ;
            g[i][j] = min(g[i - 1][g[i - 1][j]] , f[i - 1][r[f[i - 1][j]][2]]) ;
        }
    }

    for (int i = 1 ; i <= q ; i ++) {
        int c , d ;
        cin >> c >> d ;

        if (c == d) {
            cout << 1 << "\n" ;
            continue ;
        }

        int u = c + 1 , v = r[c + 1][1] ;
        int x = 1 ;

        for (int j = MAXL - 1 ; j >= 1 ; j --) {
            int gu , gv ;
            gu = min(g[j][u] , f[j][v]) ;
            gv = min(g[j][v] , f[j][r[u][2]]) ;

            if (gu > d) continue ;
            u = gu ;
            v = gv ;
            x += (1 << j) ;
        }

        if (v <= d) x ++ ;

        cout << x + 1 << "\n" ;
    }

    return 0 ;
}