Moving Points

别灰心，我一直相信着你呢。

题目链接

题目大意：给你一些点的位置，并且每个点都有一个速度，定义一个最短距离是在任何时间两点之间之间的最短距离，然后要求我们求出所有点对的最短距离的和。

这题老数据结构了。

首先我们先想到每两个点对之间的最短距离该怎样计算，由于我们每个点都有一个速度，所以我们我们两个点对之间会有一个速度差，假如这个速度差不是$0$，由于时间是无限制的，这个速度差会将两点之间的距离无限缩小或者放大，我们就可以想到两点之间的最小距离不是$0$就是他们一开始本来之间的距离，如果这个速度差是$0$ 的话。那么拿某个点来做参照物来看两点就是静止的，所以距离不会变。

判断最短距离是零还是初始之间的距离也很简单，如果前边的点走的快，那么两点之间的距离会越来越大，最短距离就是他们的初始距离，如果后边的点走的快最短距离就是$0$。

接下来我们就需要来计算了，暴力来算的话是 n 2 n^2 n2，数据范围显然不允许咱们这样做，我们可以考虑将所有的点按照距离大小进行排序，对于$i$点来说，$i$点前边的点的速度只要满足大于$i$点的速度，那么我们就可以判断他们之间的最短距离可以是$0$，要是小于的话他们之间的最短距离就是初始距离。

如果想快速实现这个我们可以用树状数组，树状数组是可以快速求前缀和， 因此我们可以将速度作为下标，然后数组里边存的是距离，我们可以按照距离从小到大遍历所有的点，由于我们是按照距离遍历的，所以我们只要寻找前方速度小于该点的点就好。可以利用前缀和来求速度小于该点的所有距离的和，我们还必须知道有前边有几个点速度小于该点的速度，所以还需要维护一个值：该速度下的点有多少个，这里注意下我们的速度范围比较大，但是个数不算特别多，所以我们可以用离散化来解决。

#include 
#include 
#include 
#include using namespace std;
typedef long long LL;const int N = 1e6 + 10, mod = 998244353;int n;
LL tr[N], cnt[N];
pair <int, int> a[N];
void add (LL tr[], int x, int c)
{for (int &i = x; i <= n * 2; i += (i & -i)) tr[i] += c;
}
LL sum (LL tr[], int x)
{LL res = 0;for (int &i = x; i ; i -= (x & -x)) res += tr[i];return res;
}
int find (vector <int> &arr, int x)
{return lower_bound (arr.begin(), arr.end(), x) - arr.begin();
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;vector <int> arr;for (int i = 1; i <= n; i ++) {cin >> a[i].first;arr.push_back(a[i].first);}for (int i = 1; i <= n; i ++) {cin >> a[i].second;arr.push_back (a[i].second);}sort (arr.begin(), arr.end());arr.erase (unique (arr.begin(), arr.end()), arr.end());sort (a + 1, a + n + 1);LL res = 0;for (int i = 1; i <= n; i ++){int t = find (arr, a[i].first) + 1, temp = find (arr, a[i].second) + 1;res += (LL)a[i].first * sum (cnt, temp) - sum (tr, temp); // 求出速度小于该点的个数和的距离。add (tr, temp, a[i].first), add (cnt, temp, 1);}printf ("%lld", res);return 0;
}

还有一种解法是用到了c++库里边的东西，一好像是个叫树stl。

这个是这个stl的讲解

这stl主要用途就是动态的维护一个有序序列，操作上有可以求出第$i$小的数字是什么，也可以根据值来求出该值在树中是第几小的，（现在我也不清楚是不是只有这两个功能）时间复杂度在$log$的级别上。

可以想想我们可以怎样来做。

维护一个有序序列，那么我们就可以知道前边速度小于该点的数目有多少个了。 但是不好求前边小于该点的距离总和是多少，还是不太好做。 我们来换种思路来想，我们可以记录下答案中每个点的距离被加或者被减了多少次，这样我们再来看看这道题目该怎样解。首先我们可以根据速度来维护一个序列，我们可以知道前边速度小于该点的数目有多少个。那么我们就可以知道这个点被加了多少次了。然后我们想这个点的距离被减了多少次呢，我们可以这样来做，我们倒着来看，即按照距离从大到小来遍历，对于后方的点，那么我们就可以知道后方点的速度大于该点的个数，我们从而可以知道该点的距离在答案中被减了多少次，这样我们的答案就出来了。

#include 
#include 
#include using namespace std;
using namespace __gnu_pbds;typedef
tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update>
ordered_set;int main() {
#ifdef _DEBUGfreopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endifint n;cin >> n;vector<pair<int, int>> p(n);for (auto &pnt : p) cin >> pnt.first;for (auto &pnt : p) cin >> pnt.second;sort(p.begin(), p.end());ordered_set s;long long ans = 0;for (int i = 0; i < n; ++i) {int cnt = s.order_of_key(make_pair(p[i].second + 1, -1));ans += cnt * 1ll * p[i].first;s.insert(make_pair(p[i].second, i));}s.clear();for (int i = n - 1; i >= 0; --i) {int cnt = int(s.size()) - s.order_of_key(make_pair(p[i].second - 1, n));ans -= cnt * 1ll * p[i].first;s.insert(make_pair(p[i].second, i));}cout << ans << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！