分析
对于 我们非常不好处理,可以考虑 分治。先按 由小到大排序。那么所有右侧的 一定大于左侧。在处理某一层时,再按 排序。这样处理答案就非常方便了。维护一个前缀和和一个后缀和。两个指针移一下。使用快排的时间复杂度为 ,可以在分治过程中归并排序从此复杂度为 。
代码
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define LL long long const int inf = 0x3f3f3f3f; int read(){ int x=0,f=0;char ch=getchar(); while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return f ? -x : x ; } const int N = 5e4+100; struct Node{ int v,x; }s[N]; int n; LL ans = 0; bool cmpx(Node a,Node b) { return a.x < b.x; } bool cmpv(Node a,Node b) { return a.v < b.v; } void cdq(int l,int r) { if(r - l == 0) return; int mid = l + r >> 1; cdq(l,mid);cdq(mid+1,r); sort(s+l,s+mid+1,cmpx); sort(s+mid+1,s+r+1,cmpx); LL s1 = 0,s2 = 0; for(int i = l;i <= mid;i++) s1 += s[i].x; LL pos = l; LL n2 = 0,n1 = mid-l+1; for(int i = mid+1;i <= r;i++) { while(pos <= mid && s[i].x > s[pos].x) { s2 += s[pos].x; s1 -= s[pos].x; pos++; n2++;n1--; } ans += 1LL * s[i].v * (s1 - s[i].x * n1); ans += 1LL * s[i].v * (s[i].x * n2 - s2); } } int main() { n = read(); for(int i = 1;i <= n;i++) { s[i].v = read();s[i].x = read(); } sort(s+1,s+1+n,cmpv); cdq(1,n); cout << ans << endl; return 0; }