题解：P10374 [AHOI2024 初中组] 操作

wrh316 · 2024-05-03 15:28:05 · 题解

题目包含重要性质：如果 oi \gets 2，那么 ri<i。也就是说调用关系不会构成环。

考虑维护每个机器的调用次数 t，初始的时候 t 为一，表示第 ci 台机器需要调用一次。此时除了编号最大的机器的调用次数是确定的，其余机器都可能不是正确的调用次数。

我们从大到小扫描每一台机器，并且将他对前面机器的影响下传。假设当前为第 i 台机器，由于机器的操作只有两种，如果是 1 操作，说明其会执行 ti 次 a _ {xi} 加上 yi 的操作，也就是相当于 a _ {xi}←a _ {xi}+ti×yi。如果是 2 操作，相当于将 [li,ri] 范围内的 t 加一。这一步显然不可以暴力，但是发现是一个区间加，可以采用打差分标记。由于扫描线是从右往左，所以在 ri 处打上加一，li-1 处打上减一标记，然后利用一个变量 sum 从右往左累和到i处即可得到 ti。累和的过程跟随扫描线一同进行，这样复杂度仅为 O(n)。

采用打差分标记代码：

t[c]++;
t[c - 1]--;

从大到小扫描每一台机器代码：

for (int i = m; i >= 1; i--) {
    ans = (ans + t[i]) % mod;
    if (type[i] == 1) a[x[i]] = (a[x[i]] + y[i] * ans) % mod;
    else {
        t[y[i]] = (t[y[i]] + ans) % mod;
        t[x[i] - 1] = (t[x[i] - 1] + mod - ans) % mod;
    }
}