题解 P7188 [CRCI2008-2009] CVJETICI

251Sec · 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;
}