运鹏分块3代码修改

Algor

2025-12-21 10:39:44

发布于：广东

17阅读

0回复

0点赞

你这份分块写法思路是对的（num 存原值、qi 做整块懒标记、f 存每块排序后的“原值”用于二分），但查询部分有几处致命 bug，会直接把答案算错/越界。

1）单点/部分块暴力时：你把 `max` 写成了 `+=`

你写的是：

if(num[i]+qi[no]<d) ans+=max(num[i]+qi[no],ans);

这会让 ans 不断累加，完全不是“取最大值”。

✅ 应该是：

if (num[i] + qi[no] < d) ans = max(ans, num[i] + qi[no]);

你在两处（同块、跨块的左右散块）都写错了。

2）整块二分时：你用 `num[...]` 去取排序数组的位置，逻辑错误

你这句：

ans=max(num[lower_bound(...)-f-lef-1]+qi[no],ans);

问题是：lower_bound 是在 排序数组 f 里找位置的，但你却拿这个位置去访问 原数组 num。

f[lef..ri] 是排序后的值序列
num[?] 的下标和排序后的位置没有对应关系

✅ 整块的前驱值应该直接从 f 里取：

3）二分位置计算/边界判断错：`xi==0` 这个判断不对

你算：

int xi = lower_bound(...) - f - lef - 1;
if(xi==0) continue;

如果前驱不存在，lower_bound 返回 lef，那么 xi = -1
你却判断 xi==0 才 continue，导致 xi=-1 时继续往下算，直接越界/取错值

✅ 正确判断应是 pos < 0：

4）答案不存在时没输出 `-1`

题目要求不存在输出 -1，你直接输出 ans（初始化成 -(1ll<<50)），会输出一个大负数而不是 -1。

你查询部分正确写法（把你的查询逻辑最小改动修好）

把 opt==1 的部分按下面改（核心就是：散块暴力用 ans=max，整块用 f 二分取 f[pos]，最后判断输出 -1）：

}else{ // opt == 1
    long long ans = -(1ll<<60);

    if(b[e]==b[c]){
        int no=b[e];
        for(int i=e;i<=c;i++){
            long long v = num[i] + qi[no];
            if(v < d) ans = max(ans, v);
        }
    }else{
        int no=b[e];
        for(int i=e;i<=r[no];i++){
            long long v = num[i] + qi[no];
            if(v < d) ans = max(ans, v);
        }
        no=b[c];
        for(int i=l[no];i<=c;i++){
            long long v = num[i] + qi[no];
            if(v < d) ans = max(ans, v);
        }

        for(no=b[e]+1; no<b[c]; no++){
            int lef=l[no], ri=r[no];
            // 找 < (d - qi[no]) 的最大值
            int pos = int(lower_bound(f+lef, f+ri+1, d - qi[no]) - (f+lef)) - 1;
            if(pos >= 0){
                ans = max(ans, f[lef + pos] + qi[no]);
            }
        }
    }

    if(ans <= -(1ll<<55)) cout << -1 << "\n";
    else cout << ans << "\n";
}