【每日一题】补档 CF487B. Strip | 数据结构杂烩 -＞ 单调队列 | 困难

题目内容

原题链接

给定一个长度为 $n$ 的数组，将这个数组进行拆分成若干个连续子数组，
使得每个子数组的最大值减去最小值小于等于 $s$ ，
且每个子数组的长度大于等于 $len$ 。

问最少可以拆分成多少个连续子数组，如果不可以，则输出 $-1$

数据范围

• $1\le n,len\le 10^5$
• $0\le s\le 10^9$
• $-10^9\le a_i\le 10^9$

题解

状态定义
$dp[i]$ 表示将前 $i$ 个数可以拆分出的最少的连续子数组。

状态转移
d p [ i ] = min ⁡ { d p [ j ] } + 1 dp[i]= \min\{dp[j]\}+1 dp[i]=min{dp[j]}+1

这里需要满足如下两个条件：
1. max ⁡ { a [ j + 1 , ⋯ , i ] } − min ⁡ { a [ j + 1 , ⋯ , i ] } ≤ s 1. \max\{a[j+1,\cdots,i]\}-\min\{a[j+1,\cdots,i]\}\leq s 1.max{a[j+1,⋯,i]}−min{a[j+1,⋯,i]}≤s
$2.i-j+1\ge len$

暴力做法

直接枚举所有的 $j$

时间复杂度：$O(n^2)$

优化做法1

考虑如何加速找到所有合法的 $j$
当 $j$ 越小，即 $[j+1,i]$ 这个区间的最大值越大，最小值越小，那么就极值之差就越有可能大于等于 $s$ 。

那么这部分就是满足二段性的，如此就可以二分。

右端点为 $i$ ，二分左端点 $j$ ，那么 $[j,i]$ 的区间极值之差如果大于 $s$ ，那么左端点应该更大，否则应该继续二分尝试减小左端点。

如此二分的时候应该快速找到区间极值，这部分用 $RMQ$ 来解决。

我们最终二分出的左端点为 $j$ ，那么需要找到区间 $[j-1,i-len]$ 中的 $dp$ 最小值。这部分因为是动态区间求最值，线段树或者优先队列懒 pop 来解决。

时间复杂度：$O(n\log n)$

优化做法2

考虑到这里很多都是求区间的极值，而且对于每个右端点，其左端点一定是单调不减的，所以可以考虑双指针。

枚举右端点 $r$，然后移动左端点 $l$，使得区间最大值减去最小值小于等于 $s$ 。

$qmax$ 是一个单调递减的队列，队头存储的是区间最大值
$qmin$ 是一个单调递增的队列，队头存储的是区间最小值

如此就可以 $O(1)$ 快速查出区间极值。

此外，我们还需要知道最终得到左端点 $l$ ，区间 $[l-1,r-len]$ 的 $dp$ 最小值。这部分同样可以用一个单调递增的队列来维护。

时间复杂度：$O(n)$

优化做法1代码一

#include <bits/stdc++.h>
using namespace std;const int N = 100010;
const int INF = 0x3f3f3f3f;
const int BIT = 17;int qmax[BIT][N];
int qmin[BIT][N];
int lg[N];
int a[N];
int n, s, len;
int dp[N];void init_rmq() {for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= n; ++j) qmax[0][j] = qmin[0][j] = a[j];for (int k = 1; k < BIT; ++k)for (int j = 1; j + (1 << k) - 1 <= n; ++j) {qmax[k][j] = max(qmax[k - 1][j], qmax[k - 1][j + (1 << (k - 1))]);qmin[k][j] = min(qmin[k - 1][j], qmin[k - 1][j + (1 << (k - 1))]);}
}int query_seg(int left, int right) {int bit = lg[right - left + 1];return max(qmax[bit][left], qmax[bit][right - (1 << bit) + 1]) - min(qmin[bit][left], qmin[bit][right - (1 << bit) + 1]);
};struct Node {int l, r;int val;
}tr[N << 2];void build(int u, int l, int r) {tr[u] = {l, r, INF};if (l == r) return;int mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}int query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return tr[u].val;}int mid = (tr[u].l + tr[u].r) >> 1;int ans = INF;if (l <= mid) ans = min(ans, query(u << 1, l, r));if (r > mid) ans = min(ans, query(u << 1 | 1, l, r));return ans;
}void modify(int u, int p, int x) {if (tr[u].l == tr[u].r) {tr[u].val = x;return;}int mid = (tr[u].l + tr[u].r) >> 1;if (p <= mid) modify(u << 1, p, x);else modify(u << 1 | 1, p, x);tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}int main()
{scanf("%d%d%d", &n, &s, &len);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);init_rmq();build(1, 0, n);// 考虑每个点 i 向左的最大值和最小值// 二分最短的，然后我需要知道这个区间里的最大值减最小值// dp[i] 表示前 i 个点需要拆分成的最少段for (int i = 1; i <= n; ++i) dp[i] = INF;dp[0] = 0;modify(1, 0, 0);for (int i = len; i <= n; ++i) {if (query_seg(i - len + 1, i) > s) continue;int left = 1, right = i - len + 1;while (left < right) {int mid = (left + right) >> 1;if (query_seg(mid, i) > s) left = mid + 1;else right = mid;}// 查 left - 1 到 i - len 的最小值dp[i] = min(dp[i], query(1, left - 1, i - len) + 1);// 单点最小值更新if (dp[i] < INF) {modify(1, i, dp[i]);}}printf("%d\n", dp[n] == INF ? -1 : dp[n]);return 0;
}

优化做法1代码二

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 100010;
const int INF = 0x3f3f3f3f;
const int BIT = 17;int qmax[BIT][N];
int qmin[BIT][N];
int lg[N];
int a[N];
int n, s, len;
int dp[N];void init_rmq() {for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= n; ++j) qmax[0][j] = qmin[0][j] = a[j];for (int k = 1; k < BIT; ++k)for (int j = 1; j + (1 << k) - 1 <= n; ++j) {qmax[k][j] = max(qmax[k - 1][j], qmax[k - 1][j + (1 << (k - 1))]);qmin[k][j] = min(qmin[k - 1][j], qmin[k - 1][j + (1 << (k - 1))]);}
}int query_seg(int left, int right) {int bit = lg[right - left + 1];return max(qmax[bit][left], qmax[bit][right - (1 << bit) + 1]) - min(qmin[bit][left], qmin[bit][right - (1 << bit) + 1]);
};int main()
{scanf("%d%d%d", &n, &s, &len);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);init_rmq();// 考虑每个点 i 向左的最大值和最小值// 二分最短的，然后我需要知道这个区间里的最大值减最小值// dp[i] 表示前 i 个点需要拆分成的最少段for (int i = 1; i <= n; ++i) dp[i] = INF;dp[0] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;for (int i = len; i <= n; ++i) {if (i == 5) {int x = 1;}if (dp[i - len] < INF) {heap.emplace(dp[i - len], i - len);}if (query_seg(i - len + 1, i) > s) continue;int left = 1, right = i - len + 1;while (left < right) {int mid = (left + right) >> 1;if (query_seg(mid, i) > s) left = mid + 1;else right = mid;}// 查 left - 1 到 i - len 的最小值while (!heap.empty() && heap.top().second < left - 1) {heap.pop();}if (!heap.empty()) {dp[i] = heap.top().first + 1;}}printf("%d\n", dp[n] == INF ? -1 : dp[n]);return 0;
}

优化做法2代码

#include <bits/stdc++.h>
using namespace std;const int N = 100010;
const int INF = 0x3f3f3f3f;
int n, s, len;
int a[N];
int dp[N];
struct Queue {int q[N]{};int hh, tt;Queue(): hh(0), tt(-1) {}void push(int x) { q[++tt] = x; }void pop_back() { --tt; }void pop_front() { ++hh; }bool empty() const { return hh > tt; }int front() const { return q[hh]; }int back() const { return q[tt]; }
}qmax, qmin, qdp;int main()
{scanf("%d%d%d", &n, &s, &len);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);memset(dp, 0x3f, (n + 1) * sizeof(int));dp[0] = 0;for (int r = 1, l = 1; r <= n; ++r) {// 找到这个区间里的最小值while (!qmin.empty() && a[qmin.back()] >= a[r]) qmin.pop_back();qmin.push(r);// 找到这个区间里的最大值while (!qmax.empty() && a[qmax.back()] <= a[r]) qmax.pop_back();qmax.push(r);// 此时区间 [l, r] 里的最小值和最大值都已确定// 我们需要使得挪动左端点，直到区间 max - min <= s// 挪动左端点就意味着 qmax 和 qmin 需要进行移动，使得 qmax 和 qmin 的值都是在 [l, r] 之间while (!qmin.empty() && !qmax.empty() && a[qmax.front()] - a[qmin.front()] > s) {l += 1;while (!qmin.empty() && qmin.front() < l) qmin.pop_front();while (!qmax.empty() && qmax.front() < l) qmax.pop_front();}if (r >= len && dp[r - len] < INF) {while (!qdp.empty() && dp[qdp.back()] >= dp[r - len]) qdp.pop_back();qdp.push(r - len);}while (!qdp.empty() && qdp.front() < l - 1) qdp.pop_front();if (r - l + 1 >= len && !qdp.empty()) {dp[r] = dp[qdp.front()] + 1;}}printf("%d\n", dp[n] == INF ? -1 : dp[n]);return 0;
}