Just Because!

Mier_Samuelle · 2026-10-21 13:15:12 · 题解

对每个 i，记 a_i=\min\{j:p_j \ge p_i-h_i\}，b_i=\max\{j:p_j \le p_i+h_i\}，则第 i 棵树向左倒覆盖的区间为 [a_i,i]，向右倒覆盖的区间为 [i,b_i]。

对于一个合法的选择方案，任意一对覆盖区间相交的已选树一定是左边的向右倒，右边的向左倒。对每个 i，记 c_i 为 i 右侧最近的可以与其相交的树。将 [a_i,i],[i,b_i] 的权值设为 1，[i,c_i] 的权值设为 2，可将原问题转化为：选择若干个不相交区间，使总权值最大。

考虑倍增。记 f_{i}(j) 为从 j 往后选总权值为 2^i 的区间能走到的最小右端点。但发现只记这个还不够，因为可能会有一个权值为 2 的区间卡在中点处，这种情况转移不到，所以额外设 g_{i}(j) 为选总权值为 2^i-1 的区间能走到的最小右端点。转移有：

其中 t_{1/2}(i) 表示往 i 后面放一个权值为 1/2 的区间能走到的最小右端点。初始有 f_0(i)=t_1(i)，g_0(i)=i。

查询 l,r 时，容易发现 l,r 一定可以选到，我们只需考虑 [l+1,r-1] 这段区间。倍增时，记当前已经选了总权值为 S 的区间，u 为选择总权值为 S 的区间后所处的最小位置，v 为选择总权值为 S-1 的区间后所处的最小位置。若要跳 2^i 步，则有：

跳到 r-1 时停下，答案为最终的 S+2。c_i 可用扫描线求。复杂度 O(n \log n+q \log n)。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
int p[MAXN], h[MAXN], a[MAXN], b[MAXN], c[MAXN], ri[MAXN], nxt1[MAXN], nxt2[MAXN], f[20][MAXN], g[20][MAXN], n, q;
vector <int> qr[MAXN];
struct BIT{
    int v[MAXN];
    void init(){
        for (int i = 1; i <= n + 1; i++){
            v[i] = n + 1;
        }
        return;
    }
    int lowbit(int x){
        return x & (-x);
    }
    void chkmin(int u, int x){
        while (u <= n){
            v[u] = min(v[u], x);
            u += lowbit(u);
        }
        return;
    }
    int query(int u){
        int res = n + 1;
        while (u){
            res = min(res, v[u]);
            u -= lowbit(u);
        }
        return res;
    }
}tr;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> h[i];
        b[i] = n + 1;
    }
    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(p + 1, p + n + 1, p[i] - h[i]) - p;
        b[a[i]] = min(b[a[i]], i);
        c[i] = upper_bound(p + 1, p + n + 1, p[i] + h[i]) - p - 1;
        qr[c[i]].push_back(i);
    }
    tr.init();
    for (int i = n; i >= 1; i--){
        for (int u : qr[i]){
            ri[u] = tr.query(n - u);
        }
        tr.chkmin(n - a[i] + 1, i);
    }
    int mn1 = n + 1, mn2 = n + 1;
    nxt1[n + 1] = nxt2[n + 1] = n + 1;
    for (int i = n; i >= 1; i--){
        nxt1[i] = mn1;
        nxt2[i] = mn2;
        mn1 = min(mn1, c[i]);
        mn1 = min(mn1, b[i]);
        mn2 = min(mn2, ri[i]);
    }
    for (int i = 1; i <= n + 1; i++){
        f[0][i] = nxt1[i];
        g[0][i] = i;
    }
    for (int i = 1; i <= 19; i++){
        for (int j = 1; j <= n + 1; j++){
            f[i][j] = min(f[i - 1][f[i - 1][j]], g[i - 1][nxt2[g[i - 1][j]]]);
            g[i][j] = min(f[i - 1][g[i - 1][j]], g[i - 1][f[i - 1][j]]);
        }
    }
    while (q--){
        int l, r;
        cin >> l >> r;
        if (r - l <= 1){
            cout << r - l + 1 << "\n";
            continue;
        }
        r--;
        int ans = 0, cura = l, curb = n + 1;
        for (int i = 19; i >= 0; i--){
            int na = min(f[i][cura], g[i][nxt2[curb]]);
            int nb = min(f[i][curb], g[i][cura]);
            if (na <= r){
                ans += (1 << i);
                cura = na;
                curb = nb;
            }
        }
        cout << ans + 2 << "\n";
    }
    return 0;
}

:::