维护时间轴

· · 算法·理论

对于一类动态修改查询的问题,通常的视角是对时间轴扫描线,对序列开数据结构维护。

事实上,我们可以变换视角,对序列下标扫描线,数据结构上维护时间轴的信息。

UOJ515 前进四

维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 i,x,令 a_i \gets x。
  • 给定 x,求 [x,n] 中严格后缀 \min 的数目。

将修改查询离线,对序列下标从 n \to 1 扫描线,数据结构上维护时间轴。

对于固定的下标 i,a_i 是关于 t 的分段常函数。所有 i 的段数总和 \le n+q。

对时间轴维护 f_t 表示在时刻 t,目前扫描过的 (i,n] 的最小值。对当前 a_i,设时间段 t \in [l,r] 时其值为 v,若 v<f_t 则 a_i 是新的后缀 \min,令 t 时刻的答案 +1 并更新 f_t \gets v 即可。

若 t 时刻有查询 [x,n],可以在扫描到 i=x 时直接提取 t 时刻的答案。

考察用于维护时间轴的数据结构,我们需要区间 chkmin,并做 chkmin 成功的位置权值 +1,查询是单点求权值。可以使用 SegBeats 维护,对最大值位置 +1 直接打标记处理。复杂度 O((n+q)\log q)。代码。

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 无法通过。

转 i-t 二维平面分析,则 a_i 是关于 t 的分段常函数,段数总和 \le n+q。每个线段对开口向上的 3-side 矩形 chkmax,询问是 2-side 矩形求和。

对 i 轴扫描线,数据结构维护时间轴。扫描线每次移动时,更新历史和拼出询问答案,故我们需要区间 chkmax,更新历史和,查询前缀历史和。

可以用 SegBeats 配合历史和半群。我们用向量—矩阵法构造半群,信息设计为 \begin{bmatrix} \sum a_i \\ H \\ \text{len}\end{bmatrix},其中 H 是历史和,\text{len} 是区间长。信息合并是对位加,修改操作为:

标记复合是矩阵乘法。进行半群优化,只维护 \begin{bmatrix} 1 & 0 & A \\ B & 1 & C\\ 0 & 0 & 1\end{bmatrix} 形式的标记即可。

现在将半群套用到 SegBeats 上。将标记分成两类,专门作用于最小值和非最小值,标记下传时对最小值和严格次小值分别处理即可。

视 n,q 同阶复杂度 O(n \log n)。代码。

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。

对序列扫描线,维护时间轴。对于每个位置 i,我们只要考察哪些操作操作了 a_i,并将其贡献累加。

题目钦定了 a_i 的上下界 [0,c_i]。想象 a_i 的变化类似一条折线,我们只要找到最后一次触碰限制的时间,将时间轴上后缀的贡献累加即可。

弱化题目,假定 c_i=+\infty 思考做法。如下图,红线表示不考虑下界的情形:

观察上图发现,绿线最后一次触碰下界的位置,一定是红线的最低点。找到最低点后,将剩余部分的贡献累加,即为绿线的最终高度。

考虑维护红线,也就是在维护原序列时记录前缀和,线段树上二分找到前缀和最低点,查询是后缀求和。特别地,若最小前缀和 \ge 0,说明红线没有触碰下界,此时全局求和为答案。

一般地,考虑 c_i 的限制是在纵轴上新增了一条反射线:

在折线图上刻画双线反射的性质。注意到,在上下限的两次反射中,红线的高差必然超过 c_i。

对应到红线的实际意义,则是前缀和的极差 >c_i。因此,我们仍可以在线段树上二分找到最右侧点,并在后缀上求解单线反射的问题。

对于后缀,可以发现问题等价于只考虑上界 / 下界的情形。类比 c_i =+\infty 的解法,维护前缀和最小值 / 最大值,线段树上二分找后缀并求后缀和即可。

考虑具体实现:对于每个修改,我们在 l 处挂上插入事件,r+1 处挂上删除事件,则只要对线段树做单点修改。
线段树每个节点维护对应区间的最小 / 最大前缀和,以及区间总和,两种信息可以合并。
线段树二分时考察一侧的信息并递归所求侧,在叶节点分类讨论。这里细节较多,详细实现参见代码注释。

视 n,q 同阶,正确实现的复杂度为 O(n \log 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);
}

:::::