算法
(优化合并) $O(n)$
考虑优化合并的方法。
若当前位置为 $u$,价值为 $w$,则我们可以将其拆成两个点 $(u - w, u + w)$。于是原问题变为判断是否存在区间交,若存在则可以合并。
因此,我们可以从左往右更新,用栈存下之前存在的集合。每次枚举的时候先将栈顶能够合并的所有元素拿掉,然后将新的元素压入栈,最后统计答案即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::max;
const int N = 1e6 + 10;
struct node {
int l, r;
node(int L, int R) { l = L, r = R; }
node() { l = r = 0; }
} st[N];
node merge(node x, node y) {
return node(min(x.l, y.l), max(x.r, y.r));
}
int main() {
int n;
cin >> n;
int top = 0;
rep(i, n) {
int a;
cin >> a;
st[++top] = node(i - a + 1, i + a + 1);
while (top > 1 and st[top - 1].r >= st[top].l) {
top--;
st[top] = merge(st[top], st[top + 1]);
}
}
int ans = 0;
while (top) {
ans += (st[top].r - st[top].l + 1) / 2;
top--;
}
cout << ans << '\n';
return 0;
}
dalao怎么不在洛谷发题解
luogu现在不给发题解。三天后才行。