线段树 SOS /kel
查看原帖
线段树 SOS /kel
327385
luosw楼主2020/12/6 13:48

最后三个点 RE 了。

不好意思有强烈的代码风格

#include <bits/stdc++.h>

using namespace std;
namespace luosw {
namespace IO {
    template < typename T >
    inline T read() {
        T    ret = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            ret = ret * 10 + ch - '0', ch = getchar();
        return ret * f;
    }
    template < typename T >
    void write(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        T y = 10, len = 1;
        while (y <= x) {
            y *= 10;
            len++;
        }
        while (len--) {
            y /= 10;
            putchar(x / y + 48);
            x %= y;
        }
    }
    template < typename T >
    void write(T x, bool flag) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        T y = 10, len = 1;
        while (y <= x) {
            y *= 10;
            len++;
        }
        while (len--) {
            y /= 10;
            putchar(x / y + 48);
            x %= y;
        }
        if (flag)
            putchar('\n');
    }
}  // namespace IO
namespace tools {
    template < typename T >
    T cmax(T a, T b) {
        return max(a, b);
    }
    template < typename T >
    T cmin(T a, T b) {
        return min(a, b);
    }
    template < typename T >
    T cgcd(T a, T b) {
        return __gcd(a, b);
    }
    template < typename T >
    T clcm(T a, T b) {
        return a * b / cgcd(a, b);
    }
}  // namespace tools
}  // namespace luosw
#define int long long
int a[100005];
#define read(t) t = luosw::IO::read< int >()
#define write(t) luosw::IO::write< int >(t, true)
class SegmentTree {
  private:
    int b[100005], d[100005];

  public:
    void build(int l, int r, int p) {
        if (l == r) {
            d[p] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(l, m, p * 2), build(m + 1, r, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }
    void update(int l, int r, int c, int s, int t, int p) {
        if (l <= s && r >= t) {
            d[p] += (t - s + 1) * c, b[p] += c;
            return;
        }
        int m = (s + t) / 2;
        if (b[p]) {
            d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m), b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        }
        b[p] = 0;
        if (l <= m)
            update(l, r, c, s, m, p * 2);
        if (r > m)
            update(l, r, c, m + 1, t, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }
    int getSum(int l, int r, int s, int t, int p) {
        if (l <= s && t <= r)
            return d[p];
        int m = (s + t) >> 1;
        if (b[p]) {
            d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
            b[p * 2] += b[p], b[p * 2 + 1] += b[p];
            b[p] = 0;
        }
        int sum = 0;
        if (l <= m)
            sum = getSum(l, r, s, m, p * 2);
        if (r > m)
            sum += getSum(l, r, m + 1, t, p * 2 + 1);
        return sum;
    }
    SegmentTree() {
    }
    SegmentTree(int l, int r, int p) {
        build(l, r, p);
    }
};
int    n, m;
signed main() {
    read(n);
    read(m);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
    }
    SegmentTree t(1, n, 1);
    while (m--) {
        int op, a, b;
        read(op);
        switch (op) {
            case 1: {
                read(op), read(a), read(b);
                t.update(op, a, b, 1, n, 1);
                break;
            }
            case 2: {
                read(a), read(b);
                write(t.getSum(a, b, 1, n, 1));
                break;
            }
        }
    }
#ifdef debug
    system("pause");
#endif
    return 0;
}

谢谢各位!

2020/12/6 13:48
加载中...