题目大意：给定一些牛，每头牛有一个权值和一个坐标，两头牛之间交谈需要两牛之间距离*权值较大值的音量，求所有对牛产生的音量和。
分析一下，我们要维护的值之中，距离其实有好多是重叠的，应该是可以用数据结构维护的，但是令人头疼的事情是因为每次要*权值较大的音量值，这样的话每次不知道应该选取哪个音量（不可能现比较），就难以维护。解决方法很自然，就是对音量进行排序，之后任意一头牛在与之前的牛交谈就使用ta的音量，与后面的牛交谈就用它们的音量了（就不是当前这次维护要管的事了）
我们排序后，只要计算出当前在x位置之前牛的个数和距离和，在x之后牛的个数和距离和（分别使用树状数组维护个数和距离），之后计算一下就好了。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define lowbit(x) x & (-x) using namespace std; typedef long long ll; const int M = 20005; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct cow { int x,vol; bool operator < (const cow &g) const { return vol < g.vol; } }co[M]; int n,c[M]; ll dis[M],ans; void add(int x) { while(x <= M-5) c[x]++,x += lowbit(x); } ll asksum(int x) { ll cur = 0; while(x) cur += c[x],x -= lowbit(x); return cur; } void adddis(int x,int val) { while(x <= M-5) dis[x] += val,x += lowbit(x); } ll askdis(int x) { ll cur = 0; while(x) cur += dis[x],x -= lowbit(x); return cur; } int main() { n = read(); rep(i,1,n) co[i].vol = read(),co[i].x = read(); sort(co+1,co+1+n); rep(i,1,n) { ll f = askdis(co[i].x-1),g = askdis(M-5) - askdis(co[i].x); ll p = asksum(co[i].x-1),q = asksum(M-5) - asksum(co[i].x); ans += (co[i].x * p - f + g - q * co[i].x) * co[i].vol; add(co[i].x),adddis(co[i].x,co[i].x); } printf("%lld ",ans); return 0; }