样例过了,但是提交几个WA几个RE
查看原帖
样例过了,但是提交几个WA几个RE
925044
Xia_Qian楼主2023/9/24 15:52
//
// Created by 37237 on 2023/9/24.
//
#include <bits/extc++.h>

const int maxn = 1e5 + 7;

int n, m;
std::array<int, maxn> a, d;

template<typename T = int>
class FenwickTree {
    typename std::enable_if_t<std::is_integral<T>::value, int> n{};
    std::vector<T> c, d1, d2;

    inline int lowbit(int x) {
        return x & (-x);
    }

    void _add(std::vector<T> &array, int i, const T &k) {
        assert(i > 0);
        while (i <= n) {
            array[i] += k;
            i += lowbit(i);
        }
    }

    T preSum(std::vector<T> &array, int i) {
        T sum = 0;
        while (i) {
            sum += array[i];
            i -= lowbit(i);
        }
        return sum;
    }

public:
    __attribute__((unused)) FenwickTree() : n(-1) {}

    __attribute__((unused))explicit FenwickTree(int n) : n(n), c(n + 2), d1(n + 2), d2(n + 2) {}

    __attribute__((unused))explicit FenwickTree(const std::vector<T> &init) : FenwickTree(init.size() - 1) {
        for (int i = 1; i <= n; i++) {
            c[i] += init[i];
            if (i + lowbit(i) <= n)
                c[i + lowbit(i)] += c[i];
        }
    }

    __attribute__((unused)) void reset(int num) {
        this->n = num;
        c.assign(num + 2, 0);
        d1.assign(num + 2, 0);
        d2.assign(num + 2, 0);
    }

    // 单点修改
    __attribute__((unused)) void add(int i, const T &k) {
        _add(c, i, k);
    }

    // 区间修改
    void add(int l, int r, const T &k) {
        assert(l <= r && r <= n);
        _add(d1, l, k);
        _add(d1, r + 1, -k);
        _add(d2, l, k * l);
        _add(d2, r + 1, -k * (r + 1));
    }

    // 前缀和
    T preSum(int i) {
        return preSum(c, i) + (i + 1) * preSum(d1, i) - preSum(d2, i);
    }

    // 区间和
    T intSum(int l, int r) {
        assert(r >= l);
        return preSum(r) - preSum(l - 1);
    }

    // 后缀和
    __attribute__((unused)) T sufSum(int i) {
        return intSum(i, n);
    }
};

auto main() -> int {
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a.at(i);
    }
    for (int i = 1; i <= n; ++i) {
        d.at(i) = a.at(i) - a.at(i - 1);
    }
    FenwickTree<int> TreeArray(std::vector<int>(d.begin(), d.begin() + n + 1));
    while (m--) {
        int op;
        std::cin >> op;
        switch (op) {
            case 1: {
                int l, r, K, D;
                std::cin >> l >> r >> K >> D;
                TreeArray.add(l, K);
                TreeArray.add(l + 1, r, D);
            }
                break;
            case 2: {
                int p;
                std::cin >> p;
                std::cout << TreeArray.preSum(p) << std::endl;
            }
                break;
            default: {
                break;
            }
        }
    }
}
2023/9/24 15:52
加载中...