洛谷P5094 [USACO04OPEN] MooFest G 加强版题解

题意：

每一年，约翰的 $n$ 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 $i$ 的听力为 $v_i$ ，这表示如果奶牛 $j$ 想说点什么让她听到，必须用高于 $v_i \times \mathrm{dis}(i,j)$ 的音量。因此，如果奶牛 $i$ 和 $j$ 想相互交谈，她们的音量必须不小于 $\max (v_i,v_j) \times \mathrm{dis}(i,j)$ 。其中 $\mathrm{dis}(i,j)$ 表示她们间的距离。

现在 $n$ 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 $x_i$ 。如果每对奶牛都在交谈，并且使用最小音量，那所有 $\frac{n(n-1)}{2}$ 对奶牛间谈话的音量之和为多少？

输入格式：

第 $1$ 行输入一个整数 $n$ 。

接下来 $N$ 行，每行输入两个数 $v_i$ 和 $x_i$ ，分别代表第 $i$ 头奶牛的听力和坐标。

输出格式：

输出一个数，代表这 $\frac{n(n-1)}{2}$ 对奶牛谈话时的音量之和。

数据范围：

$1 \leq N,V_i,x_i \leq 5 \times 10^4$ 。

这里讲两种做法。

解法1：树状数组。

注意到本题有两个维度，考虑按 $v$ 顺序排序，然后在 $x$ 上~~动手脚~~。

可以发现，现在的难点就变成 $\mathrm{dis}(i,j)$ 了，因为 $v_j \ge v_i(i < j)$ 时，一定是当前位置的 $j$ 产生贡献

考虑分类讨论处理 $\mathrm{dis}(i,j) = |x_i - x_j|$ 。

当 $x_j \ge x_i$ 时，我们需要统计 $j$ 前面有多少个这样的 $i$ ，然后算一算和啥的就好了，

我们可以维护两个树状数组，分别维护 $i$ 的个数和 $\sum x_i$ 。

当 $x_j < x_i$ 时，我们只需要维护一个前缀和，就可以利用之前维护的东西算出答案。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4+15))

int n,m,res,S;
struct node{ int v,x; } a[N];
struct BIT
{
    int tree[N]; int lowbit(int x) { return x & (-x); }
    void add(int x,int v) { for(int i = x; i <= m; i += lowbit(i)) tree[i] += v; }
    int qry(int x){ int ans=0; for(int i = x; i; i -= lowbit(i)) ans+=tree[i]; return ans;}
}tr[2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++){ cin >> a[i].v >> a[i].x; up(m, a[i].x); }
    sort(a + 1, a + 1 + n,[](node a, node b) { return a.v < b.v; });
    for(int i = 1; i <= n; i++)
    {
        int num = tr[0].qry(a[i].x), sum = tr[1].qry(a[i].x);
        res += (num * a[i].x - sum) * a[i].v;
        res += ((S - sum) - (i - num - 1) * a[i].x) * a[i].v;
        tr[0].add(a[i].x, 1); tr[1].add(a[i].x, a[i].x); S += a[i].x;
    }
    cout << res << '\n';
    return 0;
}

解法2：分治。

这个解法挺巧妙的，有一点CDQ分治的味道。

还是考虑将物品按 $v$ 顺序排序，然后考虑贡献。

对于区间 $[l,r]$ ，我们钦定区间 $[l, \mathrm{mid}]$ 和 $[\mathrm{mid} + 1, r]$ 都满足 $x$ 为升序排序（此时 $v$ 无序）

由于我们已经排序过了，所以 $\forall x_i \in [l, \mathrm{mid}],\exists x_j \in [\mathrm{mid} + 1, r],x_i \le x_j$ 。

回到 $[l,r]$ 。考虑固定 $j \in [\mathrm{mid} + 1, r]$ ，则一定有一个 $i$ 使得 $i$ 是最后一个满足 $x_i \le x_j$ 的位置。

则区间 $[l,j]$ 的贡献可以以下式计算（定义 $S_{[i,j]} = \sum_{t\in[i,j]} x_t$ ）

$\begin{aligned} \frac{\Delta}{v_j}&=x_j-x_l+x_j-x_{l+1}+\cdots+x_j-x_i+x_{i+1}-x_j+\cdots+x_{\text{mid}}-x_j \\[6pt]&=\sum_{k=l}^i (x_j-x_k)+\sum_{k=i+1}^{\text{mid}} (x_k-x_j) \\[6pt]&=\sum_{k=l}^i x_j-\sum_{k=l}^i x_k+\sum_{k=i+1}^{\text{mid}} x_k-\sum_{k=i+1}^{\text{mid}} x_j \\[6pt]&=x_j \times(i-l+1)-S_{[l, i]}+S_{[i+1, \text{mid}]}-x_j \times(\text{mid}-i) \end{aligned}$

时间复杂度 $\mathcal{O}(n \log n)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4+15))

int n,res,sum[N];
struct node{ int v,x; } a[N],tmp[N];
void solve(int l,int r)
{
    if(l >= r) return; sum[l - 1] = 0;
    int mid = (l + r) >> 1; solve(l, mid); solve(mid + 1, r);
    for(int i = l; i <= r; i++) sum[i] = sum[i - 1] + a[i].x;
    int i = l - 1, k = 0;
    for(int j = mid + 1; j <= r; j++)
    {
        while(a[i + 1].x <= a[j].x && i < mid){ tmp[++k] = a[++i]; } tmp[++k] = a[j];
        res += a[j].v * ((i - l + 1) * a[j].x - sum[i] + sum[mid] - sum[i] - (mid - i) * a[j].x);
    }
    while(i < mid) tmp[++k] = a[++i];
    memcpy(a + l, tmp + 1, k * sizeof(node));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].v >> a[i].x;
    sort(a + 1, a + 1 + n,[](node a, node b) { return a.v < b.v; }); 
    solve(1, n); cout << res << '\n';
    return 0;
}