[Daimayuan] 奶牛集会（C++，线段树）

题目描述

约翰的 $n$ 头奶牛每年都会参加“哞哞大会”。

哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。

它们参加活动时会聚在一起，第 $i$ 头奶牛的坐标为 $x_i$ ，没有两头奶牛的坐标是相同的。

奶牛们的叫声很大，第 $i$ 头和第 $j$ 头奶牛交流，会发出 $max\{v_i,v_j\}×|x_i−x_j|$ 的音量，其中 $v_i$ 和 $v_j$ 分别是第 $i$ 头和第 $j$ 头奶牛的听力。

假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

输入格式

第 $1$ 行：单个整数 $n$ ， $1≤n≤3×10^4$ 。

第 $2$ 行到第 $n + 1$ 行：第 $i + 1$ 行有两个整数 $v_i$ 和 $x_i$ （ $1≤v_i,x_i≤3×10^4$ ）。

输出格式

输出单个整数，表示所有奶牛产生的音量之和。

样例输入

样例输出

补充说明

原题：[USACO04OPEN] MooFest G。

虽然可以使用 $O(N^2)$ 的模拟通过本题，但为了~~保证其趣味性~~，建议使用分治或 树状数组。

双倍经验： $O(N^2)$ 过不去的加强版。

解题思路

读完题后想了想，好像找不到什么子结构可以用来优化算法。

所以直接模拟：

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
const int max_n = 3e4;long long pos[max_n], vol[max_n];int main() {int n, i, j;scanf("%d", &n);long long ans = 0;for (i = 0; i < n; i++) {scanf("%lld%lld", vol + i, pos + i);for (j = 0; j < i; j++) {ans += max(vol[i], vol[j]) * abs(pos[i] - pos[j]);}}printf("%lld\n", ans);return 0;
}

~~噫，好了，我过了。~~

然后我们尝试优化算法，使它能够通过加强版数据。

之前算法低效的根本原因是每次只能处理一对奶牛之间的交流，我们需要想办法批量处理。

对于计算公式 $max\{v_i,v_j\}×|x_i−x_j|$ ，如果在指定奶牛群中， $i$ 号奶牛的音量最大，我们就可以进行批量处理了。

所以我们将奶牛按音量排序，然后逐个加入奶牛群中。

每加入一头奶牛，累计它和其他所有奶牛的交流音量。

最后，加强版AC代码如下：

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 5e4;struct cow { long long pos, vol; }cows[max_n + 1];
long long tree1[max_n * 4], tree2[max_n * 4];	//tree1维护奶牛的位置和，tree2维护奶牛的数量void update(int idx, int l, int r, int pos, long long val, long long tree[]) {/* 在tree所维护的数组的pos位置加上val */if (l == r) {tree[idx] += val;return;}int m = l + r >> 1;if (pos <= m) update(idx << 1, l, m, pos, val, tree);else update((idx << 1) + 1, m + 1, r, pos, val, tree);tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
}long long query(int idx, int l, int r, int L, int R, long long tree[]) {/* 查询[L,R]区间和 */if (L <= l && r <= R) {return tree[idx];}int m = l + r >> 1;long long ret = 0;if (L <= m) ret += query(idx << 1, l, m, L, R, tree);if (R > m) ret += query((idx << 1) + 1, m + 1, r, L, R, tree);return ret;
}int main() {int n, i, j;scanf("%d", &n);//cin >> n;for (i = 1; i <= n; i++) {scanf("%lld%lld", &(cows[i].vol), &(cows[i].pos));//cin >> cows[i].vol >> cows[i].pos;}sort(cows + 1, cows + n + 1, [](cow c1, cow c2) {return c1.vol < c2.vol;});long long ans = 0;long long front_sum, back_sum, front_num, back_num;for (i = 1; i <= n; i++) {front_sum = query(1, 1, max_n, 1, cows[i].pos, tree1);back_sum = query(1, 1, max_n, cows[i].pos, max_n, tree1);//对于相同位置，距离为0，重复计数无影响front_num = query(1, 1, max_n, 1, cows[i].pos, tree2);back_num = query(1, 1, max_n, cows[i].pos, max_n, tree2);//对于相同位置，距离为0，重复计数无影响ans += cows[i].vol * (front_num * cows[i].pos - front_sum + back_sum - back_num * cows[i].pos);update(1, 1, max_n, cows[i].pos, cows[i].pos, tree1);update(1, 1, max_n, cows[i].pos, 1LL, tree2);}printf("%lld\n", ans);return 0;
}