美团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;
}
