Description

约翰的\(N\)头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出\(max(V_i, V_j)~\times~|X_i − X_j |\) 的音量，其中\(V_i\) 和\(V_j\) 分别是第\(i\) 头和第\(j\),头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

Input

第一行：单个整数\(N\)

第二行到第\(N + 1\) 行：第\(i + 1\) 行有两个整数\(V_i\)和\(X_i\)。

Output

单个整数：表示所有奶牛产生的音量之和

Sample Input

43 12 52 64 3

Sample Output

57

Hint

所有数据\(\leq~20000\)

Solution

发现枚举每两头奶牛是一件非常傻逼的事情。所以考虑对于每对奶牛，计算每头\(v\)更小（或更大）的牛的答案。

为了破除掉\(max\)的干扰，可以按照\(v\)升序排序，这样扫一遍数组，就可以对于每个位置只计算它之前的牛的位置差最后乘v即可。

考虑快速求出每个位置之前的x值。

对于\(i\)之前的每个\(x_j\)，共有两种，分别是大于\(x_i\)和小于\(x_i\)的。这样按照坐标建立树状数组可以统计他之前之后\(x_j\)的和以及个数，可以轻松算出该位置的ans。

Code

#include
    
     #include
     
      #define rg register#define ci const int#define cl const long long inttypedef long long int ll;namespace IO {    char buf[90];}template
      
       inline void qr(T &x) {    char ch=getchar(),lst=' ';    while(ch>'9'||ch<'0') lst=ch,ch=getchar();    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    if(lst=='-') x=-x;}template
       
        inline void write(T x,const char aft,const bool pt) {    if(x<0) x=-x,putchar('-');    int top=0;    do {        IO::buf[++top]=x%10+'0';        x/=10;    } while(x);    while(top) putchar(IO::buf[top--]);    if(pt) putchar(aft);}template
        
         inline T mmax(const T a,const T b) {if(a>b) return a;return b;}template
         
          inline T mmin(const T a,const T b) {if(a
          
           inline T mabs(const T a) {if(a<0) return -a;return a;}template
           
            inline void mswap(T &a,T &b) { T temp=a;a=b;b=temp;}const int maxn = 20010;const int upceil = 20000;struct Tree { int cnt;ll sum; inline Tree(int _a=0,ll _b=0) {cnt=_a,sum=_b;}};Tree frog[maxn];struct M { int v,x; inline bool operator<(const M &_others) const { return this->v<_others.v; }};M MU[maxn];int n;ll ans;inline int lowbit(ci x) {return x&((~x)+1);}void add(ci);Tree ask(int);int main() { qr(n); for(rg int i=1;i<=n;++i) {qr(MU[i].v);qr(MU[i].x);} std::sort(MU+1,MU+1+n); for(rg int i=1;i<=n;++i) { Tree _ans1=ask(MU[i].x),_ans2=ask(upceil); ans+=(1ll*_ans1.cnt*MU[i].x-_ans1.sum+(_ans2.sum-_ans1.sum)-1ll*(_ans2.cnt-_ans1.cnt)*MU[i].x)*MU[i].v; add(MU[i].x); } write(ans,'\n',true); return 0;}Tree ask(int x) { ll _sum=0;int _cnt=0; while(x) { _sum+=frog[x].sum; _cnt+=frog[x].cnt; x-=lowbit(x); } return Tree(_cnt,_sum);}void add(ci x) { int _c=x; while(_c<=upceil) { frog[_c].sum+=x; ++frog[_c].cnt; _c+=lowbit(_c); }}
           
          
         
        
       
      
     
    

Summary

当计算被最大值限制时，可以考虑升/降序排序一次计算该位置从而避免最大值的\(O(n^2)\)枚举