2022-05-26：void add(int L, int R, int C)代表在arr[L...R]上每个数加C， int get(int L, int R)代表查询arr[L...R]上的累加

2022-05-26：void add(int L, int R, int C)代表在arr[L…R]上每个数加C，
int get(int L, int R)代表查询arr[L…R]上的累加和，
假设你可以在所有操作开始之前，重新排列arr。
请返回每一次get查询的结果都加在一起最大能是多少。
输入参数:
int[] arr : 原始数组，
int[][] ops，二维数组每一行解释如下:
[a,b,c]，如果数组有3个数，表示调用add(a,b,c)，
[a,b]，如果数组有2个数，表示调用get(a,b)，
a和b表示arr范围，范围假设从1开始，不从0开始。
输出：
假设你可以在开始时重新排列arr，返回所有get操作返回值累计和最大是多少？
来自美团。

答案2022-05-26：

线段树。

代码用rust编写。代码如下：

fn main() {

    let mut arr: Vec<i32> = vec![1, 2, 3, 4, 5];

    let mut ops: Vec<Vec<i32>> = vec![vec![1, 3], vec![2, 4], vec![1, 5]];

    println!("ans = {}", max_gets(&mut arr, &mut ops));

}

fn max_gets(arr: &mut Vec<i32>, ops: &mut Vec<Vec<i32>>) -> i32 {

    let n = arr.len() as i32;

    let mut get_tree = SegmentTree::new(n);

    for op in ops.iter_mut() {

        if op.len() == 2 {

            get_tree.add(op[0], op[1], 1);

        }

    }

    let mut get_cnts: Vec<Vec<i32>> = vec![];

    for i in 0..n {

        get_cnts.push(vec![]);

        for _j in 0..2 {

            get_cnts[i as usize].push(0);

        }

    }

    let mut i: i32 = 1;

    let mut j: i32 = 0;

    while i <= n {

        get_cnts[j as usize][0] = j;

        get_cnts[j as usize][1] = get_tree.get(i, i);

        i += 1;

        j += 1;

    }

    get_cnts.sort_by(|a, b| a[1].cmp(&b[1]));

    arr.sort();

    let mut re_arrange: Vec<i32> = vec![];

    for _i in 0..n {

        re_arrange.push(0);

    }

    for i in 0..n {

        re_arrange[get_cnts[i as usize][0] as usize] = arr[i as usize];

    }

    let mut st = SegmentTree::new2(&mut re_arrange);

    let mut ans = 0;

    for op in ops.iter_mut() {

        if op.len() == 3 {

            st.add(op[0], op[1], op[2]);

        } else {

            ans += st.get(op[0], op[1]);

        }

    }

    return ans;

}

pub struct SegmentTree {

    pub n: i32,

    pub arr: Vec<i32>,

    pub sum: Vec<i32>,

    pub lazy: Vec<i32>,

}

impl SegmentTree {

    pub fn new(size: i32) -> Self {

        let mut n = size + 1;

        let mut sum: Vec<i32> = vec![];

        let mut lazy: Vec<i32> = vec![];

        let arr: Vec<i32> = vec![];

        for _i in 0..n << 2 {

            sum.push(0);

            lazy.push(0);

        }

        n -= 1;

        Self { n, arr, sum, lazy }

    }

    pub fn new2(origin: &mut Vec<i32>) -> Self {

        let mut n = origin.len() as i32 + 1;

        let mut arr: Vec<i32> = vec![];

        arr.push(0);

        for i in 1..n {

            arr.push(origin[(i - 1) as usize]);

        }

        let mut lazy: Vec<i32> = vec![];

        let mut sum: Vec<i32> = vec![];

        for _i in 0..n << 2 {

            sum.push(0);

            lazy.push(0);

        }

        n -= 1;

        let mut a = Self { n, arr, sum, lazy };

        a.build(1, n, 1);

        return a;

    }

    fn build(&mut self, l: i32, r: i32, rt: i32) {

        if l == r {

            self.sum[rt as usize] = self.arr[l as usize];

            return;

        }

        let mid = (l + r) >> 1;

        self.build(l, mid, rt << 1);

        self.build(mid + 1, r, rt << 1 | 1);

        self.push_up(rt);

    }

    fn push_up(&mut self, rt: i32) {

        self.sum[rt as usize] = self.sum[(rt << 1) as usize] + self.sum[(rt << 1 | 1) as usize];

    }

    fn push_down(&mut self, rt: i32, ln: i32, rn: i32) {

        if self.lazy[rt as usize] != 0 {

            self.lazy[(rt << 1) as usize] += self.lazy[rt as usize];

            self.sum[(rt << 1) as usize] += self.lazy[rt as usize] * ln;

            self.lazy[(rt << 1 | 1) as usize] += self.lazy[rt as usize];

            self.sum[(rt << 1 | 1) as usize] += self.lazy[rt as usize] * rn;

            self.lazy[rt as usize] = 0;

        }

    }

    pub fn add(&mut self, ll: i32, rr: i32, cc: i32) {

        self.add0(ll, rr, cc, 1, self.n, 1);

    }

    fn add0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {

        if ll <= l && r <= rr {

            self.sum[rt as usize] += cc * (r - l + 1);

            self.lazy[rt as usize] += cc;

            return;

        }

        let mid = (l + r) >> 1;

        self.push_down(rt, mid - l + 1, r - mid);

        if ll <= mid {

            self.add0(ll, rr, cc, l, mid, rt << 1);

        }

        if rr > mid {

            self.add0(ll, rr, cc, mid + 1, r, rt << 1 | 1);

        }

        self.push_up(rt);

    }

    pub fn get(&mut self, ll: i32, rr: i32) -> i32 {

        return self.query(ll, rr, 1, self.n, 1);

    }

    fn query(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {

        if ll <= l && r <= rr {

            return self.sum[rt as usize];

        }

        let mid = (l + r) >> 1;

        self.push_down(rt, mid - l + 1, r - mid);

        let mut ans = 0;

        if ll <= mid {

            ans += self.query(ll, rr, l, mid, rt << 1);

        }

        if rr > mid {

            ans += self.query(ll, rr, mid + 1, r, rt << 1 | 1);

        }

        return ans;

    }

}

执行结果如下：

左神java代码

2022-05-26：void add(int L, int R, int C)代表在arr[L...R]上每个数加C， int get(int L, int R)代表查询arr[L...R]上的累加的相关教程结束。