d799. 区间求和

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
3.5 kB
112
Indexable
Never
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
void build(int L, int R, int v, vector<pair<long long int, long long int>> &node, vector<long long int> &num)
{
    if (L == R)
        node[v] = make_pair(num[L], 0);
    else
    {
        int mid = (L + R) / 2;
        build(L, mid, v * 2 + 1, node, num);
        build(mid + 1, R, v * 2 + 2, node, num);
        node[v] = make_pair(node[v * 2 + 1].first + node[v * 2 + 2].first, 0);
    }
}
void update(long long int target_L, long long int target_R, long long int k, long long int v, long long int current_L, long long int current_R, vector<pair<long long int, long long int>> &node)
{
    if (target_L == current_L && target_R == current_R)
        node[v] = make_pair(node[v].first + (current_R - current_L + 1) * k, node[v].second + k);
    else
    {
        long long int mid = (current_L + current_R) / 2;
        if (target_R <= mid)
            update(target_L, target_R, k, v * 2 + 1, current_L, mid, node);
        if (mid + 1 <= target_L)
            update(target_L, target_R, k, v * 2 + 2, mid + 1, current_R, node);
        if (target_L <= mid && mid + 1 <= target_R)
        {
            update(target_L, mid, k, v * 2 + 1, current_L, mid, node);
            update(mid + 1, target_R, k, v * 2 + 2, mid + 1, current_R, node);
        }
        node[v] = make_pair(node[v].first + (target_R - target_L + 1) * k, node[v].second);
    }
}
unsigned long long int sum = 0;
void query(long long int target_L, long long int target_R, long long int lazytag, long long int v, long long int current_L, long long int current_R, vector<pair<long long int, long long int>> &node)
{
    node[v] = make_pair(node[v].first + (current_R - current_L + 1) * lazytag, node[v].second + lazytag);
    if (target_L == current_L && target_R == current_R)
        sum += node[v].first;
    else
    {
        long long int mid = (current_L + current_R) / 2;
        if (target_R <= mid)
            query(target_L, target_R, node[v].second, v * 2 + 1, current_L, mid, node);
        if (mid + 1 <= target_L)
            query(target_L, target_R, node[v].second, v * 2 + 2, mid + 1, current_R, node);
        if (target_L <= mid && mid + 1 <= target_R)
        {
            query(target_L, mid, node[v].second, v * 2 + 1, current_L, mid, node);
            query(mid + 1, target_R, node[v].second, v * 2 + 2, mid + 1, current_R, node);
        }
        node[v] = make_pair(node[v].first, 0);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<long long int> num;
    num.reserve(N);
    num.resize(N);
    for (int i = 0; i < N; i++)
        cin >> num[i];
    vector<pair<long long int, long long int>> node;
    node.reserve(4 * N);
    node.resize(4 * N);
    build(0, N - 1, 0, node, num);
    int Q;
    cin >> Q;
    for (int c = 0; c < Q; c++)
    {
        int v;
        cin >> v;
        if (v == 1)
        {
            long long int target_L, target_R, k;
            cin >> target_L >> target_R >> k;
            update(target_L - 1, target_R - 1, k, 0, 0, N - 1, node);
        }
        if (v == 2)
        {
            long long int target_L, target_R;
            cin >> target_L >> target_R;
            sum = 0;
            query(target_L - 1, target_R - 1, 0, 0, 0, N - 1, node);
            cout << sum << '\n';
        }
    }
}