学习笔记：分治处理区间最值相关的计数 / DP

CGcgxyXY · 2026-07-31 16:14:05 · 算法·理论

总述

有如下两类与区间最值 / 区间最值位置相关的问题。

第一类：
统计满足一定条件的区间个数 / 区间权值和。
例如 \sum_{l=1}^{n}\sum_{r=l}^n (\max_{i=l}^ra_i \times \min_{j=l}^r a_j)。

第二类：
有最值条件约束 / 最值贡献的动态规划。
例如 f_i=\max_{j=1}^{i-1}(f_j+\max_{k=j+1}^ia_k)。

此时可以考虑分治计算。

记当前处理的区间为 [l,r]。
取区间中点 mid=\lfloor \frac{l+r}{2} \rfloor。
对于端点都在 [l,mid] 或 (mid,r] 的区间，可以递归计算。
仅处理跨区间的答案即可。

由于跨区间，显然满足：区间一定包含中点 mid 和 mid+1。
那么可以对左区间求出后缀最值，对右区间求出前缀最值。
这样 \max_{i=l}^r a_i 就可以直接 O(1) 计算。

由于是前缀 / 后缀最值，所以最值还具有单调性。
此时就可以方便地计算贡献。

也可以拓展到最值位置，并且最值位置也有单调性。

CF1156E Special Segments of Permutation

Luogu Link。

Description

给定长度为 n 的排列 a_1,a_2,\dots,a_n。
求 \sum_{l=1}^n \sum_{r=l}^n [a_l+a_r=\max_{i=l}^r a_i]。

Solution

直接分治统计。

首先由于 a_i \in [1,n]，区间 [i,i] 肯定不满足条件，可以不统计。

时间 O(n \log^2 n)，空间 O(n)。

Code

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define ui unsigned int
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N = 1e6 + 5;
int n;
int a[N], val[N], b[N];
ui ans;
void solve(int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);
    int mx =-1145141919;
    per(i, mid, l) b[i] = max(mx, a[i] - a[i + 1]), mx = max(mx, val[i]);
    mx =-1145141919;
    rep(i, mid + 1, r) b[i] = max(mx, a[i] - a[i - 1]), mx = max(mx, val[i]);
    sort(b + l, b + mid + 1);
    sort(b + mid + 1, b + r + 1);
    int j = l;
    rep(i, mid + 1, r){
        while (j <= mid && b[j] < b[i])++j;
        ans += (ui)b[i] * (j - l);
    }
    j = mid + 1;
    rep(i, l, mid){
        while (j <= r && b[j] <= b[i])++j;
        ans += (ui)b[i] * (j - mid - 1);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) val[i] = a[i] - max(a[i + 1], a[i - 1]);
    solve(1, n);
    cout << ans << '\n';
    return 0;
}

:::

CF1849E Max to the Right of Min

Luogu Link。

Description

给定长度为 n 的序列 a_1,a_2,\dots,a_n。且保证 a_i 互不相同。
记 maxpos_{l,r} 为区间 [l,r] 最大 a_i 的下标，minpos_{l,r} 为区间 [l,r] 最小 a_i 的下标。
求 \sum_{l=1}^n\sum_{r=l}^n[maxpos_{l,r}>minpos_{l,r}]。

Solution

首先对于 l=r 的情况，有 maxpos_{l,r}=minpos_{l,r}=l=r，可以不统计。

分治统计 l<r 的情况。

从中点拆开最值位置，变成左区间的后缀最值位置和右区间的前缀最值位置。

记 mxp_i 为前 / 后缀最大值位置，mnp_i 为前 / 后缀最小值位置。
显然可以 O(len) 递推求出来。

那么再额外维护两个指针 j1,j2，使得 [l,j1] 是使得 a_{mxp_j}>a_{mxp_i} 的极长前缀，[l,j2] 是使得 a_{mnp_j}<a_{mnp_i} 的极长前缀。

枚举右端点 x，然后分讨最值的情况。

1. 两个都在左区间。此时 x \in [l,\min(j1,j2)]，需要统计的是 \sum_{ x \in [1,\min(j1,j2)]}[mxp_x>mnp_x]，额外预处理左区间 [mxp_x>mnp_x] 的前缀和即可。
2. 两个都在右区间。此时 x \in (\max(j1,j2),mid]，需要统计的是 \sum_{x \in (\max(j1,j2),mid]}[mxp_i>mnp_i]=(mid-\max(j1,j2))[mxp_i>mnp_i]。
3. 最大值在左区间，最小值在右区间。显然不满足条件。
4. 最大值在右区间，最小值在左区间。条件显然成立。此时 x \in (j1,j2]，有 \max(j2-j1,0) 个 x 合法。

时间 O(n \log n)，空间 O(n)。

Code

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N = 1e6 + 5;
int n;
int a[N];
int mxp[N], mnp[N];
int sum[N];
ll ans;
void solve(int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);
    mxp[mid] = mnp[mid] = mid, mxp[mid + 1] = mnp[mid + 1] = mid + 1;
    per(i, mid - 1, l) mxp[i] = a[i] > a[mxp[i + 1]] ? i : mxp[i + 1];
    rep(i, mid + 2, r) mxp[i] = a[i] > a[mxp[i - 1]] ? i : mxp[i - 1];
    per(i, mid - 1, l) mnp[i] = a[i] < a[mnp[i + 1]] ? i : mnp[i + 1];
    rep(i, mid + 2, r) mnp[i] = a[i] < a[mnp[i - 1]] ? i : mnp[i - 1];
    sum[mid] = 0;
    per(i, mid - 1, l) sum[i] = sum[i + 1] + (mxp[i] > mnp[i] ? 1 : 0);
    sum[l - 1] = sum[l];
    int j1 = mid, j2 = mid;
    rep(i, mid + 1, r){
        while (j1 >= l && a[mxp[j1]] < a[mxp[i]])--j1;
        while (j2 >= l && a[mnp[j2]] > a[mnp[i]])--j2;
        ans += sum[l] - sum[min(j1, j2) + 1] + (mxp[i] > mnp[i] ? 1 : 0) * (mid - max(j1, j2)) + max(j2 - j1, 0);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    solve(1, n);
    cout << ans <<  '\n';
    return 0;
}

:::

CF1482E Skyline Photo

Luogu Link。

Description

给定长度为 n 的两个序列 h,b。
记 minpos_{l,r} 为区间 [l,r] 内最小 h_i 的下标。
你需要将序列分为若干个区间，使得 \sum b_{minpos_{l,r}} 最大。
保证 h_i 各不相同。

Solution

首先显然可以 DP。
定义 f_i 为划分完前 i 个并以 i 为一个右端点的最大答案。
特别地，f_0=0。

显然有转移 f_i=\max_{1 \le j \le i}f_{j-1}+b_{minpos_{j,i}}。

考虑使用分治优化 DP。
为了方便统计，需要枚举 minpos_{l,r} 更新。

由于前面的 f_i 会更新后面的 f_j，需要保障更新 f_j 时 f_i 已经计算完毕。
只需要在分治树上中序遍历即可。

由于在转移方程中可能出现 j=i 的情况，需要在叶子节点更新 f_i=\max(f_i,f_{i-1}+b_i)。

对于其他情况，把 minpos_{l,r} 从中点拆开。
记录 pos_i 为 h 的前 / 后缀最小值位置。
可以 O(len) 递推出来。

再维护指针 j，使得 [l,j] 是满足 h_{minpos_{x,mid}}<h_{minpos_{mid+1,i}} 的极长段。

那么 \forall x \in [l,j]，minpos_{x,i}=pos_x，\forall x \in (j,mid]，minpos_{x,i}=pos_i。