70分求助
查看原帖
70分求助
101561
Jin_cpp楼主2021/10/13 00:07

本蒟蒻70分调了n天调不出来,最后三个大点全WA

#include<bits/stdc++.h>
using namespace std;
long long tree[200010], d[200010], a[200010];
long long ini(int i, int l, int r){
    if (r == l + 1){
        tree[i] = a[l];
        return tree[i];
    }
    int mid = (l + r) / 2;
    tree[i] = ini(i * 2 + 1, l, mid) + ini(i * 2 + 2, mid, r);
    return tree[i];
}
long long sum(int i, int l, int r, int x, int y){
    long long res;
    if (x <= l && y >= r){
        res = tree[i];
    }else if (x < r && y > l){
        int mid = (l + r) / 2;
        res = sum(i * 2 + 1, l, mid, x, y) + sum(i * 2 + 2, mid, r, x, y);
    }else{
        return 0;
    }
    return res + d[i] * (min(r, y) - max(l, x));
}
void add(int i, int l, int r, int x, int y, long long o){
    if (x <= l && y >= r){
        d[i] += o;
    }else if (x < r && y > l){
        tree[i] += o * (min(r, y) - max(l, x));
        int mid = (l + r) / 2;
        add(i * 2 + 1, l, mid, x, y, o);
        add(i * 2 + 2, mid, r, x, y, o);
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    ini(0, 0, n);
    for (int i = 0; i < m; i++){
        int t;
        cin >> t;
        if (t == 1){
            int x, y;
            long long k;
            cin >> x >> y >> k;
            add(0, 0, n, x - 1, y, k);
        }else{
            int x, y;
            cin >> x >> y;
            cout << sum(0, 0, n, x - 1, y) << '\n';
        }
    }
    return 0;
}

为方便各位巨佬们读懂,在此注明

  1. 怕爆int已全改为long long,但貌似没有爆
  2. 线段树区间采用0起点兼左闭右开([a,b))表示(尽量不要让我改这部分,求求了),输入时已转为0起点
  3. 节点编号采用0起点,左子树为2i+12i+1,右子树为2i+22i+2

求各位大大指点迷津!!!

2021/10/13 00:07
加载中...