LOJ #2348. 「JOI 2018 Final」美术展览
简要题意：
(n) 个艺术品，分别有尺寸 (A_i) 和价值 (B_i). 选定若干艺术品的“总价值”为 其价值之和减去尺寸的极差。极差即为最大值和最小值的差。求这个“总价值”的最大值。
(n leq 5 imes 10^5)，(1 leq A_i leq 10^{15})，(1 leq B_i leq 10^9 (1 leq i leq n)).
算法一
首先考虑一个 (mathcal{O}(n^2)) 的简易做法。
套路按 (A) 排序，贪心地，如果在已选定的若干艺术品中可以加入一个艺术品，使得该艺术品的尺寸在原来的最大值和最小值之间，那么该艺术品可以加入，这样是不用减去极差就可以加价值的操作。
所以按 (A) 排序后，选的艺术品必然是一个连续的区间，这样可以套路设 (s) 为 (B) 的前缀和，快速计算价值之和。
这样枚举左端点 (i)，扩展右端点 (j)，则 ([i,j]) 的“总价值”为：
时间复杂度：(mathcal{O}(n^2)).
算法二
考虑如何优化算法一？
套路枚举左端点 (i)，如何快速确定 (j)？
其中 (a_i - s_{i-1}) 当我们选定 (i) 后就不变了，我们需要快速求出 (max_{j=i}^n (s_j - a_j)).
令 ( ext{tmax}_i = max_{j=i}^n (s_j - a_j))，考虑如何预处理 ( ext{tmax})？
很显然，倒着枚举 (i)，用 ( ext{tmax}_{i+1}) 的结果和当前的 (s_i - a_i) 取一个较大即可。
时间复杂度：(mathcal{O}(n)).
注：这里有一个小细节。如果你这样写：
typedef long long ll;
const int N=5e5+1;
...
struct art {
ll A,B;
} a[N];
...
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].B;
for(int i=n;i>=1;i--) tmax[i]=max(tmax[i+1],s[i]-a[i].A);
将会得到错误的答案。
观察可以发现，答案可能是负数，所以 ( ext{tmax}) 也可能是负数。
而数组默认 ( ext{tmax}_{n+1} = 0)，这样会影响整个数组，因而答案错误。
所以要预先处理一个极小值。
时间复杂度：(mathcal{O}(n)).
实际得分：(100pts).
(168) 个测试点好评
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+2;
inline ll read(){char ch=getchar(); ll f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}
struct art {
ll A,B;
} a[N]; int n;
ll tmax[N],s[N];
ll ans=-(1ll<<62);
inline ll max(ll x,ll y) {return x>y?x:y;}
inline bool cmp(art x,art y) {
return x.A<y.A;
}
int main() {
n=read(); tmax[n+1]=ans; // ans 此时为极小值
for(int i=1;i<=n;i++) a[i].A=read(),a[i].B=read();
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].B;
for(int i=n;i>=1;i--) tmax[i]=max(tmax[i+1],s[i]-a[i].A);
for(int i=1;i<=n;i++) ans=max(ans,a[i].A-s[i-1]+tmax[i]);
printf("%lld
",ans);
return 0;
}