1 条题解
-
0
T4 连续段(consecutive)题解
题意简述
给定一个 到 的排列。称子数组 为连续段,若 。对每个前缀 ,求其中连续段的数量。
思路
固定右端点
固定右端点 ,对每个左端点 定义
$$f_r(l)=\max_{l\le i\le r}a_i-\min_{l\le i\le r}a_i-(r-l).$$因为 是排列,子数组中的 个数互不相同,且都落在 内,所以
$$\max-\min+1\ge r-l+1\quad\Longrightarrow\quad f_r(l)\ge 0.$$而 时 ,故 。于是
因此,若我们能对每个 维护所有 ,那么“以 结尾的连续段数量”就是 中 的 的个数。
从 到
加入 时, 会发生三类变化:
- 长度项: 比 少 ,所以所有 的 都减 ;
- 最大值项: 用单调递减栈维护最大值。当 大于栈顶时,弹出栈顶 。设弹出后栈顶为 (空则为 ),则对于 ,最大值从 变成 , 增加 ;
- 最小值项: 用单调递增栈维护最小值。当 小于栈顶时,弹出栈顶 。设弹出后栈顶为 ,则对于 ,最小值从 变成 , 增加 。
每个下标最多入栈、出栈一次,所以总共有 次区间加操作。
线段树
用线段树维护 ,支持:
- 区间加;
- 查询区间内最小值以及最小值出现的次数。
因为 且 ,所以区间 的最小值一定是 ,最小值出现次数就是 的 的个数,也就是以 结尾的连续段数量。
把每个 的答案累加,就得到每个前缀的答案。
正确性证明
引理 1: 对任意 ,。
子数组中有 个互不相同的整数,全部在 中,因此区间 至少包含 个整数,即 。
引理 2: 线段树在扫描到 时,叶子 的值恰好等于 (对 )。
对 归纳。 时 ,初始值正确。从 到 :
- 长度项统一减 ;
- 单调栈弹出一段时,这段左端点的最大值确实从 变为 ,其余位置的最大值不变;
- 最小值同理。 三类修改恰好覆盖 的所有变化,因此归纳成立。
引理 3: 扫描到 时, 中 的 的个数等于以 结尾的连续段数量。
由 与连续段定义的等价性直接得到;又因为 且 ,区间最小值为 ,线段树返回的最小值个数正是零的个数。
定理: 对每个前缀 ,累加 的答案,得到的就是前缀 中所有连续段的数量。
每个连续段有唯一的右端点 ,按右端点分类计数再求和即可。
复杂度
每个下标最多入栈、出栈一次,线段树每次区间加/查询 。
总时间复杂度 ,空间复杂度 。
参考代码(C++)
#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct SegTree { int n; vector<int> mn, cnt, lazy; SegTree(int n) : n(n), mn(4 * n + 5), cnt(4 * n + 5), lazy(4 * n + 5) { build(1, 1, n); } void build(int p, int l, int r) { cnt[p] = r - l + 1; mn[p] = 0; if (l == r) return; int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); } void apply(int p, int v) { mn[p] += v; lazy[p] += v; } void push(int p) { if (lazy[p]) { apply(p << 1, lazy[p]); apply(p << 1 | 1, lazy[p]); lazy[p] = 0; } } void pull(int p) { if (mn[p << 1] < mn[p << 1 | 1]) { mn[p] = mn[p << 1]; cnt[p] = cnt[p << 1]; } else if (mn[p << 1] > mn[p << 1 | 1]) { mn[p] = mn[p << 1 | 1]; cnt[p] = cnt[p << 1 | 1]; } else { mn[p] = mn[p << 1]; cnt[p] = cnt[p << 1] + cnt[p << 1 | 1]; } } void add(int ql, int qr, int v) { add(1, 1, n, ql, qr, v); } void add(int p, int l, int r, int ql, int qr, int v) { if (ql <= l && r <= qr) { apply(p, v); return; } push(p); int mid = (l + r) >> 1; if (ql <= mid) add(p << 1, l, mid, ql, qr, v); if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, v); pull(p); } pair<int, int> query(int ql, int qr) { return query(1, 1, n, ql, qr); } pair<int, int> query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return {mn[p], cnt[p]}; push(p); int mid = (l + r) >> 1; if (qr <= mid) return query(p << 1, l, mid, ql, qr); if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr); auto L = query(p << 1, l, mid, ql, qr); auto R = query(p << 1 | 1, mid + 1, r, ql, qr); if (L.first < R.first) return L; if (L.first > R.first) return R; return {L.first, L.second + R.second}; } }; int main() { freopen("consecutive.in", "r", stdin); freopen("consecutive.out", "w", stdout); int n; if (scanf("%d", &n) != 1) return 0; vector<int> a(n + 1); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); SegTree seg(n); vector<int> mxStack, mnStack; vector<long long> ans(n + 1); long long total = 0; for (int r = 1; r <= n; r++) { if (r > 1) seg.add(1, r - 1, -1); while (!mxStack.empty() && a[mxStack.back()] < a[r]) { int idx = mxStack.back(); mxStack.pop_back(); int left = mxStack.empty() ? 1 : mxStack.back() + 1; seg.add(left, idx, a[r] - a[idx]); } mxStack.push_back(r); while (!mnStack.empty() && a[mnStack.back()] > a[r]) { int idx = mnStack.back(); mnStack.pop_back(); int left = mnStack.empty() ? 1 : mnStack.back() + 1; seg.add(left, idx, a[idx] - a[r]); } mnStack.push_back(r); total += seg.query(1, r).second; ans[r] = total; } for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]); return 0; }易错点
- 查询区间必须是 ,不能是 : 的位置没有定义,线段树中仍为 ,如果查询整个数组会把它们错误地计入。
- 最小值个数只有在最小值为 时才有意义:代码依赖 ,所以区间最小值必为 ;若查询区间不含 ,这个性质不成立。
- 单调栈的修改区间是 : 是弹出后的新栈顶(空则为 ),不是 。
- 长度项只对 减 : 的新位置初始就是 ,不能一起减。
- 中间值可能暂时为负:先做 再做最大值/最小值更新,更新过程中线段树可能出现负值,但查询发生在所有更新之后,最终 。
- 答案要用
long long:递增排列的答案为 , 时约为 。 - :答案为 ,代码自然处理。
测试点设计
测试点 设计意图 1 样例 1,基本计数 2 样例 2,前缀答案递增 3 ,答案为 4 的递减排列,答案为 5 的递增排列,答案为三角数 6 的递减排列,答案同样为三角数 7 的随机排列 8 的随机排列 9 的随机排列 10 ,由大量递增小块打乱而成,连续段数量较多 11 的“锯齿”排列 ,答案恰为 ,检验边界 12 的递增排列,答案达到 ,强制使用 long long
- 1
信息
- ID
- 9
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者