本文迁移自洛谷原文。
CF372C Watching Fireworks is Fun
我们可以换种思考方式来解决这个问题。
显然 是一个很无关紧要的东西，我们可以把它们先全部累加到 里。然后题目就变成了要让 最大，所以就可以看为要使得 最小。
令 表示考虑到某个时间点，此时你的坐标为 的最小的 。
假设我们已经考虑了前 场烟花，此时我们要考虑加入第 场烟花带来的影响。
令 ，则我们就相当于执行 。
然后每燃放一场烟花，我们就相当于对 加上一个 的函数。
综上，可以发现，这个 是一个折线函数，且段数是 的，计算相邻时间和加入新烟花秀都可以在 的时间内解决，故我们得到了一个时间复杂度为 的做法。
考虑继续优化。
发现这个 的每条折线的斜率从左往右可以看作依次为 。
这启发我们可以维护两个优先队列一样的东西，一个维护左半段斜率小于 的部分的转折点的 坐标，另一个维护右半段的东西。
我们考虑在这种维护方式下，等待时间和加入烟花秀各有什么影响。
由于这个 是先降后增的，所以这个等待一段时间就变得非常好处理。就是让 中的所有元素减去 ， 中的所有元素加上 ，中间多出一段斜率为 的段。
当然，我们没有必要真的去减一遍，我们只需要维护两个全局减去/加上的 和 ，每次就让 ，然后再 中加入新元素的时候就加入 。
再考虑这个加入烟花的操作。
令左半段最右边的转折点横坐标为 ，右半段最左边的转折点横坐标为 。
此时就相当于 都多了一个转折点 ，都push。
此时 的最右边的转折点就成为了 ，且斜率为 的转折点消失了，但不妨碍我们维护，因为我们可以想象它和斜率为 的转折点重合了。
所以我们加入两边 至 ，然后把 加到 即可。
和上一种情况同理。
综上，时间复杂度 ，可以加强到 ，甚至比原题的单调队列优化dp好写的多。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,d,ans,tag,pre;
priority_queue<int>L;
priority_queue<int,vector<int>,greater<int> >R;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>d;
for(int i=1;i<=m;++i){
int a,b,t;cin>>a>>b>>t;
ans+=b;
if(i==1)L.push(a),R.push(a),pre=t;
else{
tag+=d*(t-pre);
int l=L.top()-tag,r=R.top()+tag;
if(a<l)L.pop(),L.push(a+tag),L.push(a+tag),R.push(l-tag),ans-=l-a;
else if(a>r)R.pop(),R.push(a-tag),R.push(a-tag),L.push(r+tag),ans-=a-r;
else L.push(a+tag),R.push(a-tag);
}
pre=t;
}
cout<<ans<<'\n';
}
|