悬关求调

thinkerliu @ 2023-09-24 23:09:07

#include <bits/stdc++.h>

constexpr auto MAXN = 5000050;

long long marks[MAXN << 2], nums[MAXN], a[MAXN];

int get_lchild(int now)
{
    return now << 1;
}

int get_rchild(int now)
{
    return now << 1 | 1;
}

void build_tree(int now, int l, int r)
{
    marks[now] = 0;

    if (l == r)
    {
        nums[now] = a[l];
        return;
    }

    auto mid = (l + r) >> 1;
    build_tree(get_lchild(now), l, mid);
    build_tree(get_rchild(now), mid + 1, r);

    nums[now] = nums[get_lchild(now)] + nums[get_rchild(now)]; // 向上更新(push_up)
}

void f(int now, int l, int r, int k)
{
    marks[now] += k;
    nums[now]  += k * (r - l + 1);
}

void push_down(int now, int l, int r)  // 向下更新
{
    auto mid = (l + r) >> 1;
    f(get_lchild(now), l, mid, marks[now]);
    f(get_lchild(now), mid + 1, r, marks[now]);

    marks[now] = 0;
}

void update(int now, int l, int r, int op_l, int op_r, int op_k) // op_l, op_r为要修改的区间
{
    if (op_l <= l && r <= op_r)
    {
        f(now, l, r, op_k);
        return;
    }

    push_down(now, l, r);

    auto mid = (l + r) >> 1;
    if (op_l <= mid)
    {
        update(get_lchild(now), l, mid, op_l, op_r, op_k);
    }

    if (op_r > mid)
    {
        update(get_rchild(now), mid + 1, r, op_l, op_r, op_k);
    }

    nums[now] = nums[get_lchild(now)] + nums[get_rchild(now)];
}

long long query(int now, int l, int r, int q_l, int q_r) // query -> 查询
{
    if (q_l <= l && r <= q_r)
    {
        return nums[now];
    }

    long long ans = 0;

    push_down(now, l, r);

    auto mid = (l + r) >> 1;
    if (q_l <= mid)
    {    
        ans += query(get_lchild(now), l, mid, q_l, q_r);
    }

    if (q_r > mid)
    {
        ans += query(get_rchild(now), mid + 1, r, q_l, q_r);
    }

    return ans;
}

int n, m, op, x, y, k;
int main()
{
    std::ios::sync_with_stdio(false);

    std::cin >> n >> m;
    for (auto i = 1; i <= n; i++)
    {
        std::cin >> a[i];
    }

    build_tree(1, 1, n);
    for (auto i = 1; i <= m; i++)
    {
        std::cin >> op;

        if (op == 1)
        {
            std::cin >> x >> y >> k;

            update(1, 1, n, x, y, k);
        }
        else
        {
            std::cin >> x >> y;

            std::cout << query(1, 1, n, x, y) << std::endl;
        }
    }

    return 0;
}

by Forebear @ 2023-09-24 23:23:51

pushdown第二个应该是getrchild

by Forebear @ 2023-09-24 23:25:19

#include <bits/stdc++.h>

constexpr auto MAXN = 5000050;

long long marks[MAXN << 2], nums[MAXN], a[MAXN];

int get_lchild(int now)
{
    return now << 1;
}

int get_rchild(int now)
{
    return now << 1 | 1;
}

void build_tree(int now, int l, int r)
{
    marks[now] = 0;

    if (l == r)
    {
        nums[now] = a[l];
        return;
    }

    auto mid = (l + r) >> 1;
    build_tree(get_lchild(now), l, mid);
    build_tree(get_rchild(now), mid + 1, r);

    nums[now] = nums[get_lchild(now)] + nums[get_rchild(now)]; // 向上更新(push_up)
}

void f(int now, int l, int r, int k)
{
    marks[now] += k;
    nums[now]  += k * (r - l + 1);
}

void push_down(int now, int l, int r)  // 向下更新
{
    auto mid = (l + r) >> 1;
    f(get_lchild(now), l, mid, marks[now]);
    f(get_rchild(now), mid + 1, r, marks[now]);//!

    marks[now] = 0;
}

void update(int now, int l, int r, int op_l, int op_r, int op_k) // op_l, op_r为要修改的区间
{
    if (op_l <= l && r <= op_r)
    {
        f(now, l, r, op_k);
        return;
    }

    push_down(now, l, r);

    auto mid = (l + r) >> 1;
    if (op_l <= mid)
    {
        update(get_lchild(now), l, mid, op_l, op_r, op_k);
    }

    if (op_r > mid)
    {
        update(get_rchild(now), mid + 1, r, op_l, op_r, op_k);
    }

    nums[now] = nums[get_lchild(now)] + nums[get_rchild(now)];
}

long long query(int now, int l, int r, int q_l, int q_r) // query -> 查询
{
    if (q_l <= l && r <= q_r)
    {
        return nums[now];
    }

    long long ans = 0;

    push_down(now, l, r);

    auto mid = (l + r) >> 1;
    if (q_l <= mid)
    {    
        ans += query(get_lchild(now), l, mid, q_l, q_r);
    }

    if (q_r > mid)
    {
        ans += query(get_rchild(now), mid + 1, r, q_l, q_r);
    }

    return ans;
}

int n, m, op, x, y, k;
int main()
{
    std::ios::sync_with_stdio(false);

    std::cin >> n >> m;
    for (auto i = 1; i <= n; i++)
    {
        std::cin >> a[i];
    }

    build_tree(1, 1, n);
    for (auto i = 1; i <= m; i++)
    {
        std::cin >> op;

        if (op == 1)
        {
            std::cin >> x >> y >> k;

            update(1, 1, n, x, y, k);
        }
        else
        {
            std::cin >> x >> y;

            std::cout << query(1, 1, n, x, y) << std::endl;
        }
    }

    return 0;
}

by thinkerliu @ 2023-09-28 21:27:56

感谢啊啊啊

by thinkerliu @ 2023-09-28 21:28:14

已关