Train Hard, Win Easy

做法：前缀和，贪心

思路

• 由题意可知，我们可以根据排序,即 贪心思想

• 可以根据前缀和的思想先把每个人与他人的答案求出来（如果不考虑不愿意配对的情况）
  设自己排序后的位置为i
  前i个选自己的x以及他人的y最优
  第i个之后的选自己的y以及他人的x最优

• 然后再减去不愿意配对的情况
  考虑他们两个排序后位置的前后情况，是减去谁的x，谁的y

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=300010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m;

struct node{
    ll x,y,id;
}s[N];

vector<int> g[N];

ll sumx[N],sumy[N];
ll pos[N],ans[N];
bool cmp(node a,node b){
    return a.x-a.y<b.x-b.y;
}

void solve(){
    cin>>n>>m;
    rep(i,1,n){
        cin>>s[i].x>>s[i].y;
        s[i].id=i;
    }
    while(m--){
        int u,v;cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    sort(s+1,s+1+n,cmp);
    rep(i,1,n){
        pos[s[i].id]=i;
        sumx[i]=sumx[i-1]+s[i].x;
    }
    per(i,n,1) sumy[i]=sumy[i+1]+s[i].y;
    rep(i,1,n) ans[s[i].id]=(s[i].y*(i-1)+sumx[i-1])+(s[i].x*(n-i)+sumy[i+1]);

    for(int i=1;i<=n;i++){
        for(int j:g[i]){
            if(pos[i]<pos[j]) ans[i]-=s[pos[i]].x+s[pos[j]].y;
            else ans[i]-=s[pos[i]].y+s[pos[j]].x;
        }
        cout<<ans[i]<<" \n"[i==n];
    }
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}