1 尾部追加模型
前缀最值 只能直接查询前缀最大值。若要求一般区间的最大值,需要进一步拆分块。
本篇处理一个明确的模型:数组初始为空,每次只在尾部追加一个数,已加入的数不再修改;查询当前任意非空区间
沿用旧版文章的块拆分思路,另外保存原数组:
保留
2 区间查询
从右端点
分两种情况:
- 若
,整个块都在查询内,取 ,令 。 - 若
,块跨过左边界,不能整体使用。只取 ,令 。
long long range_max(int l, int r) {
long long res = numeric_limits<long long>::lowest();
while (l <= r) {
if (r - lowbit(r) + 1 >= l) {
res = max(res, c[r]);
r -= lowbit(r);
} else {
res = max(res, a[r]);
--r;
}
}
return res;
}
每步取走当前剩余区间的一个完整后缀,既不会越界,也不会遗漏。取走部分的最大值累积在 res 中;区间为空时就得到原查询的最大值。
2.1 拆分示例
查询
它们覆盖
3 尾部追加
追加到位置
设
因为
例如追加到位置
据此实现:
void append(long long v) {
++n;
a[n] = c[n] = v;
for (int step = 1; step < lowbit(n); step <<= 1) {
c[n] = max(c[n], c[n - step]);
}
}
新块只依赖已经构建好的旧块,所以可从空数组开始逐个追加。每个块都由自身元素和互不重叠的子块合并而来,始终保持正确的块最大值。
4 复杂度
一次追加合并至多
上面的区间查询最坏为
例如查询
一般查询中,取完整块会清除一个二进制位;整块越界后的单点退回,则使当前可跨越的块长上限下降。块长有
两份数组需要
5 例题:最大数
luogu P1198: [JSOI2008] 最大数 要求维护一个初始为空的数组:
A x:将追加到尾部,其中 是最近一次查询答案,初始为 。 Q L:查询末尾个数的最大值,并更新 。
查询区间为
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5; // 按追加次数上限设置
int n;
long long a[maxn], c[maxn];
int lowbit(int x) { return x & -x; }
void append(long long v) {
++n;
a[n] = c[n] = v;
for (int step = 1; step < lowbit(n); step <<= 1) {
c[n] = max(c[n], c[n - step]);
}
}
long long range_max(int l, int r) {
long long res = numeric_limits<long long>::lowest();
while (l <= r) {
if (r - lowbit(r) + 1 >= l) {
res = max(res, c[r]);
r -= lowbit(r);
} else {
res = max(res, a[r]);
--r;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
long long mod, last = 0;
cin >> m >> mod;
while (m--) {
char op;
long long x;
cin >> op >> x;
if (op == 'A') {
long long v = x % mod;
if (v < 0) v += mod;
append((v + last) % mod);
} else {
int length = int(x);
last = range_max(n - length + 1, n);
cout << last << '\n';
}
}
return 0;
}
代码将负数的余数规范到
5.1 示例
输入:
7 100
A 3
A 7
Q 2
A 5
Q 2
A -20
Q 1
输出:
7
12
92
第一次查询后
6 修改限制
这份实现只支持尾部追加,不支持修改已有位置。
旧值变小时,旧块最大值可能失效。仅重算当前块、再沿父链取更大值,无法清除父块中的旧最大值,不能据此声称支持任意赋值。
另外,最大值查询的初值应为负无穷。固定写成
7 练习
完成 luogu P1198: [JSOI2008] 最大数,再手算数组 a 还是 c,答案应为
解释:为什么在查询
8 相关题解
暂无相关题解