题意：
给出n的质点，带着初位置和速度；
如果中途两点可以相遇dis（i，j）=0；
如果不可以相遇，mindis（i，j）；
求n个点的两两质点最小dis（i,j）之和
思路：
因为当初位置x和速度v都比另一个小的时候，他们才不会相遇，所以最小的初位置想减也是abs（xi-xj）
因为速度-10^8<=v<=10^8的范围，需要离散化
将初位置进行从小到大排序，进行循环，他的速度（设v1）在所有速度的哪个位置（设pos），x1代表v1这个初始值
那么在这个位置pos之前的树状数组里存着的也是比x1小的初位置的值，用cnt[][0]存比x1小同时比v1小的点有几个，用cnt[][1]存比x1小同时比v1小的点初始值之和
每个点（初始值从小到大）的贡献x1*get（pos，0）-get（pos，1）；
最后存add（pos，x1）
树状数组1~n存的是离散化后的速度，相当于从小到大进行1~ni编号。中间可能有重复ni可能小于n
#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline #define it register int #define inf 0x3f3f3f3f #define lowbit(x) (x)&(-x) #define mem(a,b) memset(a,b,sizeof(a)) #define mod 998244353 const int maxn=2e5+10; int n,t,m; struct node{ int x,v; friend bool operator<(const node a,const node b){ if(a.x==b.x){ return a.v<b.v; } return a.x<b.x; } }a[maxn]; int v[maxn]; ll cnt[maxn][2]; il void add(int x,int val){ for(it i=x;i<=n;i+=lowbit(i)){ cnt[i][0]++; cnt[i][1]+=(ll)val; } return ; } il ll get(int x,int k){ ll sum=0; while(x){ sum+=cnt[x][k]; x-=lowbit(x); } return sum; } int main(){ scanf("%d",&n); for(it i=0;i<n;i++){ scanf("%d",&a[i].x); } for(it i=0;i<n;i++){ scanf("%d",&a[i].v); v[i]=a[i].v; } sort(a,a+n);sort(v,v+n); ll ans=0; for(it i=0;i<n;i++){ int pos=upper_bound(v,v+n,a[i].v)-v; ans+=(ll)a[i].x*get(pos,0)-get(pos,1); add(pos,a[i].x); } printf("%lld ",ans); return 0; }
这场让我上了蓝，但不得不说降智场，D题在用bfs做，写了整整一个半小时，然后wa，后面其实都能做但就是比赛的时候不敢，也容易慌
这场前三题半小时不到就完成了，然后看到F比E过的还多，瞄了一眼F，想了想把速度从1~n编码就又去想D了。然后想歪了
upd贴一张第一次上蓝
