自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 21:16:44，当前版本为作者最后更新于2024-10-21 01:24:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题考查数组的综合应用，idea 来源就是在 校门外的树 基础上，加入了更多下标范围 $\pm 1$ 的考查。

考虑用 tr[i] 表示第 $i$ 棵树是否被破坏，gr[i] 表示第 $i,i+1$ 棵树之间的草坪是否被破坏。（这里建议写一个注释，否则你可能会忘记 gr[i] 表示 $i,i+1$ 之间的草坪还是 $i,i-1$ 之间的草坪）。

接下来分类讨论一下每种操作分别对树和草坪产生了什么影响：

• 1 l r 破坏了第 $l+1\sim r-1$ 棵树。
• 2 l r 破坏了第 $l\sim r$ 棵树。
• 无论是 1 l r 还是 2 l r，都破坏了 $l\sim l+1,l+1\sim l+2,\ldots, r-1\sim r$ 这些草坪。注意这对应 gr[l] 到 gr[r-1]。

用一个循环嵌套（外层表示这是第几个施工，内层对产生的破坏进行记录），最后统计剩下的树和草坪数量即可。

注意，统计总数时，树看的是 tr[1],...,tr[m]，然而草坪看的是 gr[1],...,gr[m-1]。