46分求救
查看原帖
46分求救
969215
sdu_de_caiji楼主2023/10/12 21:09
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
#define lb(x) (x&-x)
ll sNum[maxn]={0};
ll sSum[maxn]={0};
struct cow{
    ll v,x;
    bool operator<(cow w){
        return this->v<w.v;
    }
};
ll res=0;
int n;
vector<cow> c;

ll askNum(ll p){
    ll temp_res=0;
    for(ll i=p;i>=1;i-=lb(i)){
        temp_res+=sNum[i];
    }
    return temp_res;
}
ll askSum(ll p){
    ll temp_res=0;
    for(ll i=p;i>=1;i-=lb(i)){
        temp_res+=sSum[i];
    }
    return temp_res;
}

void updNum(ll p){
    for(ll i=p;i<=n;i+=lb(i)){
        sNum[i]++;
    }
}
void updSum(ll p, ll v){
    for(ll i=p;i<=n;i+=lb(i)){
        sSum[i]+=v;
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        ll vv,xx;
        cin>>vv>>xx;
        c.push_back({vv,xx});
    }
    sort(c.begin(),c.end());
    for(int i=0;i<c.size();i++){
        int pos=c[i].x;
        updNum(pos);
        updSum(pos,pos);
        res+=c[i].v*((askNum(pos-1)- askNum(0))*pos- (askSum(pos-1)- askSum(0)))+c[i].v*(askSum(n)- askSum(pos)-pos*(askNum(n)- askNum(pos)));
    }
    cout<<res<<endl;
    return 0;
}
2023/10/12 21:09
加载中...