1.答案要取连续的区间疯狂暗示线段树。
2.外层枚举r，内层枚举l显然过于暴力。
3.考虑内层的优化。dp[i]：以第i位为结尾的答案（长度大于1的）。dp[i] = max(第一种情况，第二种情况)。解释一下，首先我们可以做到求出i前面gap[j] > gap[i]，j < i最大的j的位置pos，然后其中第一种情况为：自力更生，区间pos～i内gap[i]是最大的。这种情况可以使用线段树logn得到区间内最大右子段和；其中第二种情况为：寄人篱下，区间从pos前的某一位一直到i，即最大的gap不是gap[i]。这种直接dp转移，dp[pos] + sum[pos + 1 ~ i]即可。
4.怎样不暴力枚举巧妙得到pos？这里提供单调栈的方式，每个元素都只进出一次，复杂度完全可以承受。
5.注意一些细节，比如最大右子段可能只有一位的长度，所以代码中用pos～i-1的右子段加上了第i位的值以保证长度大于1.
6.为啥非得dp长度大于1的？因为等于1的跟gap没关系了，没法这么搞，且长度为1的……完全可以一开始读入的时候就更新掉。
7.请结合代码细细体会。
8.另一种非dp做法：因为答案的maxgap肯定只在n-1个里面选，所以枚举这n-1个gap，然后区间咋选呢，就是：对于这个gap[i]，我们可以做到求出两个数组l[i]和r[i]，其实和上一个做法很像，l[i]就是gap[i]还能做“土皇帝”向左走得最远的位置，再往左走他就不是最大的了；同理r[i]是向右走的最远。这样只要用线段树查询l[i]到r[i]的最大连续子段和即可。注意有可能i不在这个连续子段和里，但是没关系，这样算出来的值比答案更劣因为减去gap的平方减多了，而我们一会儿就会枚举到真正的答案并更新了。啊对了，l和r数组是在枚举之前用单调栈预处理的，跟dp的那个一样的……网上题解用非dp方法的很多了。
非dp代码咕咕咕，dp代码主要部分：
1 const int maxn = 3e5 + 5; 2 int n; 3 ll a, d[maxn], c[maxn], dp[maxn], ans; 4 5 class SegmentTree { 6 public: 7 #define ls(p) p << 1 8 #define rs(p) p << 1 | 1 9 10 struct Node { 11 int l, r; 12 ll rs, sum; 13 }t[maxn << 2]; 14 15 void Push_Up(int p) { 16 t[p].sum = t[ls(p)].sum + t[rs(p)].sum; 17 t[p].rs = max(t[rs(p)].rs, t[ls(p)].rs + t[rs(p)].sum); 18 } 19 20 void Build(int l, int r, int p) { 21 t[p].l = l, t[p].r = r; 22 if (l == r) { 23 t[p].rs = t[p].sum = c[l]; 24 return; 25 } 26 int mid = (l + r) >> 1; 27 Build(l, mid, ls(p)); 28 Build(mid + 1, r, rs(p)); 29 Push_Up(p); 30 } 31 32 friend Node operator + (const Node x, const Node y) { 33 return (Node){x.l, y.r, max(y.rs, x.rs + y.sum), x.sum + y.sum}; 34 } 35 36 Node Query(int l, int r, int p) { 37 if (l <= t[p].l && t[p].r <= r) { 38 return t[p]; 39 } 40 int mid = (t[p].l + t[p].r) >> 1; 41 if (r <= mid) return Query(l, r, ls(p)); 42 if (mid < l) return Query(l, r, rs(p)); 43 return Query(l, r, ls(p)) + Query(l, r, rs(p)); 44 } 45 }T; 46 47 int main() { 48 read(n), read(a); 49 50 rep(i, 1, n) { 51 read(d[i]); 52 read(c[i]); 53 c[i] = a - c[i]; 54 ans = max(ans, c[i]); 55 } 56 57 T.Build(1, n, 1); 58 59 rep(i, 1, n) c[i] += c[i - 1]; 60 61 stack<pair<ll, int>> stk; 62 63 rep(i, 2, n) { 64 int pos; 65 while (!stk.empty() && stk.top().first < d[i] - d[i - 1]) { 66 stk.pop(); 67 } 68 if (stk.empty()) pos = 1; 69 else pos = stk.top().second; 70 stk.push(make_pair(d[i] - d[i - 1], i)); 71 72 dp[i] = T.Query(pos, i - 1, 1).rs + c[i] - c[i - 1] - (d[i] - d[i - 1]) * (d[i] - d[i - 1]); 73 if (pos != 1) dp[i] = max(dp[i], dp[pos] + c[i] - c[pos]); 74 ans = max(dp[i], ans); 75 } 76 77 writeln(ans); 78 79 return 0; 80 }