萌新求大佬帮调
查看原帖
萌新求大佬帮调
608228
TXYveronica楼主2023/11/30 16:00
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 500005;

int arr[MAXN]; // 原始数列
int c1[MAXN]; // 树状数组1,用于维护原始数列
int c2[MAXN]; // 树状数组2,用于维护差分数组

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

void add(int c[], int i, int d, int n) {
    while (i <= n) {
        c[i] += d; // 更新当前节点的影响
        i += lowbit(i); // 更新父亲节点
    }
}

int pre_sum(int c[], int i) {
    int s = 0;
    while (i > 0) {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

// 区间 [x, y] 增加 k
void range_add(int x, int y, int k, int n) {
    add(c1, x, k, n);
    add(c1, y + 1, -k, n);

    add(c2, x, k * (x - 1), n);
    add(c2, y + 1, -k * y, n);
}

// 查询第 x 个数的值
int query(int x) {
    return pre_sum(c1, x) * x - pre_sum(c2, x);
}

signed main() {
    int n, m; // 数组大小和操作个数
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        range_add(i, i, arr[i], n);
    }

    for (int i = 0; i < m; ++i) {
        int op, x, y, k;
        cin >> op >> x;
        if (op == 1) {
            cin >> y >> k;
            range_add(x, y, k, n);
        } else {
            cout << query(x) << endl;
        }
    }

    return 0;
}
2023/11/30 16:00
加载中...