洛谷P5094 [USACO04OPEN] MooFest G 加强版 题解
题目链接: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)\)
代码:
#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)\)
代码:
#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;
}
参考文献: