自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:27:28，当前版本为作者最后更新于2023-08-30 15:59:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

点开题以为是毒瘤题，看完题发现是搞笑题。

可以发现长出来一个植物 $[l,r]$ 的时候，它会覆盖 $[l+1,r-1]$ 这个区间，同时长出来的花的个数正好是覆盖 $l$ 和 $r$ 这两个位置的植物个数之和。于是写个树状数组，区间加单点查询，就做完了。

写完发现过不了样例，然后意识到少看了一个条件，就是已经长出花的位置不会再长出来花。于是每次长出来新植物之后还要把 $l$ 和 $r$ 这两个位置的权值赋为 $0$。然后就对了。

#include <bits/stdc++.h>
using namespace std;
int f[100005];
void Modify(int i, int w) {
    for (; i <= 100000; i += i & -i) f[i] += w;
}
void Modify(int l, int r, int w) {
    Modify(r + 1, -w); Modify(l, w);
}
int Query(int i) {
    int res = 0;
    for (; i; i &= i - 1) res += f[i];
    return res;
}
int m;
int main() {
    scanf("%d", &m);
    while (m--) {
        int l, r; scanf("%d%d", &l, &r);
        int ql = Query(l), qr = Query(r);
        printf("%d\n", ql + qr);
        Modify(l + 1, r - 1, 1);
        Modify(l, l, -ql);
        Modify(r, r, -qr);
    }
    return 0;
}