Day 5 二分答案、ST 表与静态区间查询

今天有两条主线：

不知道答案是多少，但能判断“某个答案是否可行” -> 二分答案。
数组不修改，却有很多区间最值查询 -> ST 表。

1. 二分答案：二分的不是数组下标

普通二分是在有序数组中找位置。二分答案是在答案范围中找最大或最小的可行值。

例如：

最小的 x，使所有任务能在 x 天内完成；
最大的 k，使某个收益目标还能达到。

1.1 使用前必须确认单调性

若 check(x) 表示“答案为 x 时可行”，二分要求它具有单调性：

小答案可行，大答案不可行；
或小答案不可行，大答案可行。

先写一句话说明：

当 x 变大时，为什么 check(x) 只会从真变假，或只会从假变真？

说不清单调性，就不要急着二分。

1.2 求最大可行值模板

int l = L, r = R, ans = L - 1;
while(l <= r){
    int mid = l + (r - l) / 2;
    if(check(mid)){
        ans = mid;
        l = mid + 1;
    }else{
        r = mid - 1;
    }
}

1.3 常见边界

• check 内的和、乘积常需 long long；
• 先判断“永远不可行”和“无穷大”这类特殊答案；
• mid 用 l+(r-l)/2，避免极端情况下相加溢出；
• 明确最后求的是最大可行还是最小可行。

2. ST 表：静态区间最值的 O(1) 查询

ST 表适用于：

数组不修改；
查询很多；
操作是 min、max、gcd、按位 and/or 等幂等操作。

幂等的意思是：

min(x,x)=x，max(x,x)=x，gcd(x,x)=x。

所以两个长度为 2^k 的区间可以重叠，答案不会重复计算出错。

2.1 定义

st[k][i] = 从 i 开始、长度为 2^k 的区间答案。

转移：

st[k][i] = op(st[k-1][i], st[k-1][i + 2^(k-1)])

查询 [l,r]，令：

k = floor(log2(r-l+1))

则：

answer = op(st[k][l], st[k][r-2^k+1])

2.2 区间最大值模板

const int N = 200000 + 10;
const int LOG = 19;
int st[LOG][N], lg[N];

void build(int n){
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int k = 1; (1 << k) <= n; k++){
        for(int i = 1; i + (1 << k) - 1 <= n; i++){
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
}

int queryMax(int l, int r){
    int k = lg[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

复杂度： 建表 O(n log n)，每次查询 O(1)，空间 O(n log n)。

不能用 ST 表的情况： 数组频繁修改，或区间求和。和不是幂等操作，重叠两段会重复计数；动态数组应考虑树状数组或线段树。

3. 两道入门二分题

3.1 474B：前缀和上找第一个覆盖位置

第 i 堆虫子的编号范围由前缀和决定：

pre[i-1] < q <= pre[i]

因此要找第一个满足 pre[i] >= q 的 i：

int pos = lower_bound(pre + 1, pre + n + 1, q) - pre;

lower_bound：第一个 >= x 的位置。

3.2 600B：统计不超过 x 的元素个数

把数组 a 排序。对每个查询 x，要找第一个大于 x 的位置：

int cnt = upper_bound(a.begin(), a.end(), x) - a.begin();

upper_bound：第一个 > x 的位置。

两者对照：

4. 923B：二分每堆雪何时融完

第 i 天新出现体积 v[i] 的雪。温度前缀和：

sumT[j] = t[1] + ... + t[j]

雪堆 i 在最早的 pos 天融完，当且仅当：

sumT[pos] - sumT[i-1] >= v[i]

等价于：

sumT[pos] >= sumT[i-1] + v[i]

所以在单调的温度前缀和中二分 pos。

对于从第 i 天到 pos-1 天仍完整融化的雪堆，用差分数组维护“当天有多少堆贡献完整温度”；在 pos 天再单独加最后一点零头。

这题的结构：

每个对象的结束时间 -> 二分；
大量对象的持续贡献 -> 差分；
结束当天的特殊值 -> 单独记录。

注意： v[i]、t[i] 可以为 0，温度前缀和允许相等，二分仍然要写正确。

5. 1709D：能否跨过障碍

机器人每次恰好走 k 格。可达需要三件事：

1. 行差和列差都能被 k 整除；
2. 从起点向上跳若干次能达到的最高行，必须高于路径上最高障碍；
3. 起点和终点本身均可站立。

最高可达行：

long long top = xs + (n - xs) / k * k;

查询列区间 [min(ys,yf), max(ys,yf)] 的最高障碍，就是 ST 表区间最大值。

判定核心：

if(abs(xs - xf) % k || abs(ys - yf) % k) NO;
else if(queryMax(l, r) >= top) NO;
else YES;

这里 >= top 是因为高度为 h 的列封锁第 1..h 行，机器人必须走在严格高于 h 的行。

6. 1548B：差分数组把“同余”变成 GCD

一段数模某个 m>=2 同余，等价于相邻差的绝对值 GCD 大于 1：

a[l] ≡ a[l+1] ≡ ... ≡ a[r] (mod m)
<=> m 整除每个相邻差
<=> gcd(|a[l]-a[l+1]|, ..., |a[r-1]-a[r]|) > 1

于是原数组长度为 len 的朋友组，对应差分数组长度为 len-1 的区间。

做法：

1. 建绝对差数组；
2. 用 GCD ST 表查询任意差分区间；
3. 双指针维护最大的 GCD >1 区间。

要特别处理 n=1，答案是 1。

7. 1462F：固定中心线段后，其他线段要么在左，要么在右

假设保留 [l,r] 作为“中心线段”。不能与它相交的线段只有两类：

右端点 < l：完全在左边；
左端点 > r：完全在右边。

对所有左端点、右端点分别排序。枚举每条中心线段时：

左侧数量 = lower_bound(rightEnds, l)
右侧数量 = n - upper_bound(leftEnds, r)

两者相加就是删除数，取最小。

这题提醒我们：先固定一个关键对象，其他对象的分类往往会变得非常简单。

8. 1691D：先找最大值负责的范围

题目要求任意子数组满足：

子数组和 <= 子数组最大值

不要枚举所有子数组。对于每个 a[i]，用单调栈找到它作为最大值时能负责的最大区间 [L,R]：

左边第一个 > a[i] 的位置之后；
右边第一个 > a[i] 的位置之前。

在这个范围中，只要能找到一个包含 i 的子数组和大于 a[i]，就失败。

用前缀和后：

sum[l..r] = pre[r] - pre[l-1]

最大子数组和可拆成“右侧前缀最大值 - 左侧前缀最小值”。因此可以预处理前缀和的区间最小/最大值，再用 ST 表查询。

这类题的通用结构：

单调栈确定每个元素的支配区间；
前缀和把区间和改成两个前缀值之差；
RMQ 快速取最值。

9. 本日自查

• 二分前，我能证明 check 的单调性吗？
• lower_bound 和 upper_bound 是否选对？
• ST 表数组是否真的不修改？操作是否幂等？
• 区间端点是闭区间还是半开区间？
• 前缀和、乘积、坐标是否需要 long long？

10. 今日口诀

答案能判且单调，二分范围别二分数组。
静态最值用 ST，重叠两段要求幂等。
前缀和上找位置，lower 和 upper 分清楚。
单调栈先定边界，区间最值再来辅助。