美团4.1春招笔试编程题

第一题：排列一个数组，使得两两差值的绝对值和最小

贪心，数组排序之后，相邻两两相减，注意答案可能会爆int，开long long。

第二题：有一组展品，每个展品有价值，一共进行m次操作，操作为0时修改展品价值，操作为1时查看展品价值和

使用树状数组，抽象出问题模型就是一个单点修改、区间查询的模板。

#include <bits/stdc++.h>

using i64 = long long;

const int N = 50010;

int n, m;
int o[N], tr[N];
std::pair<int, int> p[N];

void add(int x, int k) {
  for (int i = x; i <= n; i += i & -i) {
    tr[i] += k;
  }
}

i64 sum(int x) {
  i64 ret = 0;
  for (int i = x; i; i -= i & -i) {
    ret += tr[i];
  }
  return ret;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(nullptr);
  
  std::cin >> n >> m;
  for (int i = 0; i < m; i++) {
    std::cin >> o[i];
  }
  for (int i = 0; i < m; i++) {
    std::cin >> p[i].first;
  }
  for (int i = 0; i < m; i++) {
    std::cin >> p[i].second;
  }
  
  std::vector<i64> ans;
  for (int i = 0; i < m; i++) {
    if (o[i] == 0) {
      add(p[i].first, -(sum(p[i].first) - sum(p[i].first - 1)));
      add(p[i].first, p[i].second);
    } else {
      ans.push_back(sum(p[i].second) - sum(p[i].first - 1));
    }
  }
  
  for (int i = 0; i < ans.size(); i++) {
    std::cout << ans[i] << " \n"[i == ans.size() - 1];
  }
  
  return 0;
}