维护时间轴
stripe_python · · 算法·理论
对于一类动态修改查询的问题,通常的视角是对时间轴扫描线,对序列开数据结构维护。
事实上,我们可以变换视角,对序列下标扫描线,数据结构上维护时间轴的信息。
UOJ515 前进四
维护长为
n 的序列a_i ,支持q 次操作:
- 给定
i,x ,令a_i \gets x 。- 给定
x ,求[x,n] 中严格后缀\min 的数目。
将修改查询离线,对序列下标从
对于固定的下标
对时间轴维护
若
考察用于维护时间轴的数据结构,我们需要区间 chkmin,并做 chkmin 成功的位置权值
P11368 [Ynoi2024] After god
维护两个长为
n 的序列a_i,b_i ,初始全为0 ,支持q 次操作,给定x,v ,令a_x \gets v ,对k=1,2,\cdots,n 令b_k \gets b_k+\max \limits_{i=1}^k a_i ,查询\sum \limits_{i=1}^x b_i 。
对着题意做需要单侧递归线段树维护历史和,复杂度 2log 无法通过。
转
对
可以用 SegBeats 配合历史和半群。我们用向量—矩阵法构造半群,信息设计为
- 区间
+v :\begin{bmatrix} \sum (a_i+v) \\ H \\ \text{len}\end{bmatrix}=\begin{bmatrix} 1 & 0 & v \\ 0 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix} \sum a_i \\ H \\ \text{len}\end{bmatrix} 。 - 更新历史和:
\begin{bmatrix} \sum a_i \\ H+\sum a_i \\ \text{len}\end{bmatrix}=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix} \sum a_i \\ H \\ \text{len}\end{bmatrix} 。
标记复合是矩阵乘法。进行半群优化,只维护
现在将半群套用到 SegBeats 上。将标记分成两类,专门作用于最小值和非最小值,标记下传时对最小值和严格次小值分别处理即可。
视
P8518 [IOI 2021] 分糖果
给定
c_1 \sim c_n 。维护一个长为n 的序列a_i ,q 次操作给定l,r,v ,对i \in [l,r] 令a_i \gets \max(0, \min(c_i, a_i+v)) 。初始\forall i, a_i=0 。所有操作结束后,求出
a_1 \sim a_n 。
对序列扫描线,维护时间轴。对于每个位置
题目钦定了
弱化题目,假定
观察上图发现,绿线最后一次触碰下界的位置,一定是红线的最低点。找到最低点后,将剩余部分的贡献累加,即为绿线的最终高度。
考虑维护红线,也就是在维护原序列时记录前缀和,线段树上二分找到前缀和最低点,查询是后缀求和。特别地,若最小前缀和
一般地,考虑
在折线图上刻画双线反射的性质。注意到,在上下限的两次反射中,红线的高差必然超过
对应到红线的实际意义,则是前缀和的极差
对于后缀,可以发现问题等价于只考虑上界 / 下界的情形。类比
考虑具体实现:对于每个修改,我们在
线段树每个节点维护对应区间的最小 / 最大前缀和,以及区间总和,两种信息可以合并。
线段树二分时考察一侧的信息并递归所求侧,在叶节点分类讨论。这里细节较多,详细实现参见代码注释。
视
:::::info[代码]
const int N = 2e5 + 5;
int n, m, a[N], c[N], v[N];
vector<int> A[N], D[N];
struct node {i64 sum, mx, mn;};
node operator+ (const node& a, const node& b) {
return {a.sum + b.sum, max(a.mx, a.sum + b.mx), min(a.mn, a.sum + b.mn)};
}
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
node val[N << 2];
node all() {return val[1];}
void pushup(int rt) {val[rt] = val[ls] + val[rs];}
void update(int x, i64 c, int l = 1, int r = m, int rt = 1) {
if (l == r) return val[rt] = {c, max(0LL, c), min(0LL, c)}, void();
int mid = (l + r) >> 1;
if (x <= mid) update(x, c, l, mid, ls);
else update(x, c, mid + 1, r, rs);
pushup(rt);
}
i64 ask(i64 c, node x, int l = 1, int r = m, int rt = 1) {
// x 是后缀信息
if (l == r) {
node y = val[rt] + x;
return val[rt].sum + x.mx - y.mn > c ? // sum+x.mx 右侧最高点,y.mn 区间最低点
c + x.sum - x.mx : // 最后一次触碰上界,相对变化量 x.sum-x.mx
x.sum - x.mn; // 最后一次触碰下界,相对变化量 x.sum-x.mn
}
int mid = (l + r) >> 1;
node y = val[rs] + x; // y = 右子树信息 + 后缀信息
return y.mx - y.mn > c ? // 若条件成立,说明所求位置在右子树
ask(c, x, mid + 1, r, rs) : // 递归右子树
ask(c, y, l, mid, ls); // 后缀信息为 y,递归左子树
}
} T;
void solve() {
for (int i = 1; i <= n; i++) {
for (int id : A[i]) T.update(id, v[id]);
for (int id : D[i]) T.update(id, 0);
if (T.all().mx - T.all().mn <= c[i]) a[i] = T.all().sum - T.all().mn;
else a[i] = T.ask(c[i], node{});
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size(), m = l.size();
copy(c.begin(), c.end(), ::c + 1);
for (int i = 0; i < m; i++) {
l[i]++, r[i]++, ::v[i+1] = v[i];
A[l[i]].emplace_back(i+1), D[r[i]+1].emplace_back(i+1);
}
solve();
return vector<int>(a + 1, a + n + 1);
}
:::::