自动搬运

查看原文

来自洛谷，原作者为

	wrh316 Zeit und Raum trennen dich und mich.Informatik verbindet dich und mich. || 一只可爱王法~

搬运于2025-08-24 22:57:21，当前版本为作者最后更新于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;
	}
}