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

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代码