求调,才对了一个点,感觉写的没有问题呀
查看原帖
求调,才对了一个点,感觉写的没有问题呀
1169915
miku010123楼主2024/8/19 17:47
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+10;

struct node
{
    int v;
    int x;
    bool operator<(const node&t)const 
    {
        return this->v<t.v;
    }
    /* data */
};

struct tr
{
    int sum;
    int cnt;
    /* data */
};

node a[N];
tr s[N];
int n;

int lowbit(int x)
{
    return x&-x;
}

void change(int x,int k)
{
    while(x<N)
    {
        s[x].sum+=k;
        s[x].cnt++;
        x+=lowbit(x);
    }
}

tr query(int x)
{
    int sum=0,cnt=0;
    while(x)
    {
        sum+=s[x].sum;
        cnt+=s[x].cnt;
        x-=lowbit(x);
    }
    return (tr){sum,cnt};
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].v>>a[i].x;
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        tr l=query(a[i].x-1),r=query(a[i].x+1),m=query(a[i].x);
        ans+=(a[i].x*l.cnt-l.sum)*a[i].v+(r.sum-m.sum-(r.cnt-m.cnt)*a[i].x)*a[i].v;
        change(a[i].x,a[i].x);
    }
    cout<<ans;
    return 0;
}


2024/8/19 17:47
加载中...