[JOI2017/2018]美術展

题目大意：

有\(n(n\le5\times10^5)\)个物品，每个物品有两个属性：尺寸\(A_i\)和收益\(B_i\)。从中选取一个子集，总收益为\(\sum B_i-\max\{A_i\}-\min\{A_i\}\)。求总收益最大值。

思路：

将所有物品按照\(A_i\)排序，\(B_i\)前缀和记作\(S_i\)。答案相当于\(\max\{S_i-A_i+A_j-S_{j-1}\}\)。维护\(A_j-S_{j-1}\)前缀\(\max\)即可。

源代码：

#include
    
     #include
     
      #include
      
       typedef long long int64;inline int64 getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int64 x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=5e5+1;struct Node {    int64 a,b;    bool operator < (const Node &rhs) const {        return a