本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-16 21:09:19

题目

考察：树状数组，线段树，动态规划。
题意简述：
有 $n+1$ 个城市，编号为 $[0,n]$，你接到了 $m$ 个关于一个活动的消息：$t_i,p_i$。
$t_i$ 表示该活动在第 $t_i$ 个城市举办，$p_i$ 表示参加活动可以获得的钱数，但是每经过一个城市，你要花费 $c$ 元的路费。
你一开始在 $0$ 号城市，每个活动你可以参加，也可以不参加，但必须按顺序参加，求获得的钱数的最大值。
数据范围：

• $1\le n,m\le 2\times 10^5$
• $1\le c\le 10^9$
• $1\le t_i\le n$
• $1\le p_i\le 10^{13}$

我们可以看出明显是一道 dp 题，然后 $f_i$ 肯定跟 $f_j\ \ (0\le j<i)$ 有关，很容易推出状态转移方程：
$$f_i=\max_{j=0}^{i-1}(f_j-c\times|x_i-x_j|+p_i)$$ 但是这样转移是 $O(m^2)$ 的，无法通过 $m\le 2\times 10^5$ 的数据，考虑优化。

每个点造成的贡献是 $f_j-c\times|x_i-x_j|+p_i$，其中 $p_i$ 是固定的，那么在 $f_j-c\times|x_i-x_j|$ 中，我们考虑如何拆掉绝对值符号，我们分类讨论 $|x_i-x_j|$：

• 当 $x_i\ge x_j$ 时：
  $$\begin{aligned}c\times|x_i-x_j|&=c\times(x_i-x_j)\&=c\times x_i-c\times x_j\end{aligned}$$ $c\times x_i$ 是固定的，那么我们只需要找出 $-c\times x_j$ 的最大值即可。
• 当 $x_i<x_j$ 时： $$\begin{aligned}c\times|x_i-x_j|&=c\times(x_j-x_i)\&=c\times x_j-c\times x_i\end{aligned}$$ $-c\times x_i$ 是固定的，那么我们只需要找出 $c\times x_j$ 的最大值即可。

那么我们可以用树状数组或线段树维护 $f_{x_j}\ (x_j\le x_i)$ 的前缀最大值，$f_{x_j}\ (x_j>x_i)$ 的后缀最大值（由于树状数组只能维护前缀最大值，所以我们将 $f_{x_j}$ 变为 $f_{n-x_j}$）
我们定义两个树状数组，$f$ 是维护 $x_j\le x_i$ 的最大值，查询的结果是 $fmax$，$g$ 是维护 $x_j>x_i$ 的最大值，查询的结果是 $gmax$，那么 $f_i$ 就等于： $$f_i=\max(fmax+c\times x_i,gmax-c\times x_i)+p_i$$ 然后我们在修改 $f,g$ 中的值即可。

这样我们就可以在 $O(m\log_2n)$ 的复杂度内完成本题。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define fst; ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,c,m,t,p,num,ans; 
struct BIT{
	int a[N];
	inl BIT(){
		memset(a,-0x3f,sizeof(a));
	}
	inl int lowbit(int x){
		return x&(-x);
	}
	inl void add(int x,int k){
		while(x<=n){
			a[x]=max(a[x],k);
			x+=lowbit(x);
		}
		return;
	}
	inl int getmax(int x){
		int mx=-INF;
		while(x){
			mx=max(mx,a[x]);
			x-=lowbit(x);
		}
		return mx;
	}
}t1,t2;
signed main(){
	fst; 
	cin>>n>>c>>m;
	t1.add(1,c);
	t2.add(n,-c);
	rep(i,1,m){
		cin>>t>>p;
		num=max(t1.getmax(t)-c*t,t2.getmax(n-t)+c*t)+p;
		ans=max(ans,num);
		t1.add(t,num+c*t);
		t2.add(n-t+1,num-c*t);
	}
	cout<<ans;
	return 0;
}