#P2345. [USACO04OPEN] MooFest G

    ID: 1321 Type: RemoteJudge 1000ms 125MiB Tried: 1 Accepted: 1 Difficulty: 3 Uploaded By: Tags>模拟2004USACO树状数组cdq 分治

[USACO04OPEN] MooFest G

题目背景

P5094 [USACO04OPEN] MooFest G 加强版

题目描述

约翰的 nn 头奶牛每年都会参加“哞哞大会”。

哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。

它们参加活动时会聚在一起,第 ii 头奶牛的坐标为 xix_i,没有两头奶牛的坐标是相同的。

奶牛们的叫声很大,第 ii 头和第 jj 头奶牛交流,会发出 max{vi,vj}×xixj\max\{v_i,v_j\}\times |x_i − x_j | 的音量,其中 viv_ivjv_j 分别是第 ii 头和第 jj 头奶牛的听力。

假设每对奶牛之间同时都在说话,请计算所有奶牛产生的音量之和是多少。

输入格式

第一行:单个整数 nn1n2×1041\le n\le2\times 10^4

第二行到第 n+1n + 1 行:第 i+1i + 1 行有两个整数 viv_ixix_i1vi,xi2×1041\le v_i,x_i\le2\times 10^4)。

输出格式

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

4
3 1
2 5
2 6
4 3
57