T1：

　　与模拟54T4较为相像，然而需要注意的点有所不同

首先比较显然的是DP方程：fi = fj + ai - (i - j) * (i - j - 1) / 2

常规思路为直接使用权值数据结构进行维护，然而无法处理后面的部分

考场上想过分块线段树树状数组，然而都失败了，于是突然发现对于 一点i

若i的可选部分中j为max，那么j之后的部分一定不会在成为max，于是考虑采用链表

通过截断链表的方式排除较劣值（仍然未想到斜率优化单调栈），然而发现问题一在于如何寻找前驱后继

我采用multiset维护，然而问题二在于前驱后继在本题中并不唯一，甚至可能形成环状结构，于是思路结束

通过昨天T1，我考虑能否降低维护的准确度以此换来信息的灵活性，然而仍然无法维护

　　事实上正解的思路并不是单纯的数据结构维护信息，而是决策单调性

类似模拟54T4，考虑在计算fi时j比k更优的情况（仍然套路的直接解不等式）化简得到：

设gi = fi - i * (i - 1) / 2

　　i > -(gj - gk) / (j - k)（i为常量，其余为变量）

根据>可以得出应维护右下凸包，同时递增

于是类似昨天T4的思路采取CDQ分治，利用左侧更新右侧

考虑首先消去a这一维，直接按a排序即可，接着在分治过程中按下标排序即可

注意点：首先模拟54未说的

单调队列的维护过程中，需要保证head >= tail，因为当队列中之存在一个点时，实际上还存在这原点，

这两个点的存在是的仍然能继续更新答案（可能需要特判横坐标相同的情况，或者在排序时修改排序函数）

而在单调队列获取答案的时候，则需要保证head > tail，因为当队列中仅存在一个点时，当取两点进行斜率比较时

将会取到head + 1，进行比较，而显然head + 1为队外元素（即非法），因此仅当队列中至少存在两个元素时才能弹队

　　其次是CDQ分治的顺序

模拟54T4中是先分治两侧，目的是保证有序，而本题需要先分治左侧，处理完当前区间后再处理右侧

原因在于模拟54T4的转移是不需要顺序的，只需要将前缀中所有元素进行转移即可

而对于本题而言，转移是存在顺序的，即必须从左往右转移，因为每个点需要继承之前点的贡献

（所以由于处理完当前区间后排序已经被打乱，需要重新对右区间进行排序）

　　另外还有一个不同点在于维护顺序

模拟54T4是先维护完单调栈再从右侧区间逐一进行弹栈取答案，原因在于其取答案并没有限制，即对于右侧区间所有点，取答案的条件是统一的

而对于本题而言，需要一边维护单调队列，一边取答案，因为显然，对于右侧区间内某点i，取答案的一个条件为id(j) < id(i)，也就是说右侧区间取答案的条件不统一

可以发现，若先维护队列再取答案，由于弹队列不存在id限制，那么可能对于i点的可行答案会被弹走，因此会漏情况

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I long long
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define LL long long
 8 #define P pair<I,I>
 9 #define MP make_pair
10 #define fir first
11 #define sec second
12 #define g(x) (f[x] - x * (x + 1) / 2)
13 const I N = 1e5 + 3;
14 I n,q[N],ans(LONG_LONG_MIN),f[N];
15 struct L {I a,b;} a[N];
16 inline I read() {
17     I x(0),y(1); C z(getchar());
18     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
19     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
20     return x * y;
21 }
22 inline V Max (I &a,I b) { a = a > b ? a : b; }
23 inline V Min (I &a,I b) { a = a < b ? a : b; }
24 inline I max (I a,I b) { return a > b ? a : b; }
25 inline I min (I a,I b) { return a < b ? a : b; }
26 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
27 inline B com1 (const L &a,const L &b) { 
28     return a.a == b.a ? a.b < b.b : a.a < b.a; 
29 }
30 inline B com2 (const L &a,const L &b) { return a.b < b.b; }
31 inline B Check1 (I i,I j,I k) {
32     return (g(i) - g(j)) * (j - k) >= (g(j) - g(k)) * (i - j);
33 }
34 inline B Check2 (I k,I i,I j) {
35     return k * (i - j) >= g(j) - g(i); 
36 }
37 V Divide (I l,I r) {
38     if (l == r) return ;
39     I mid (l + r >> 1),h(1),t(0),p1(l);
40     Divide (l,mid); 
41     sort (a + l,a + mid + 1,com2);
42     sort (a + mid + 1,a + r + 1,com2);
43     for (I i(mid + 1);i <= r; ++ i) {
44         while (p1 <= mid && a[p1].b < a[i].b) {
45             while (h <= t && Check1 (a[p1].b,a[q[t]].b,a[q[t - 1]].b)) t -- ; q[++t] = p1 ++ ; 
46         }
47         while (h <  t && Check2 (a[i].b,a[q[h + 1]].b,a[q[h]].b)) h ++ ;
48         if (h > t) continue;
49         Max (f[a[i].b],f[a[q[h]].b] + a[i].a - (a[i].b - a[q[h]].b) * (a[i].b - a[q[h]].b - 1) / 2);
50     }
51     sort (a + mid + 1,a + r + 1,com1);
52     Divide (mid + 1,r);
53 } 
54 signed main () {
55     freopen ("skip.in","r",stdin);
56     freopen ("skip.out","w",stdout);
57     n = read();
58     for (I i(1);i <= n; ++ i) 
59         a[i] = (L){read(),i}; 
60     for (I i(1);i <= n; ++ i)
61         f[i] = a[i].a - i * (i - 1) / 2;
62     sort (a + 1,a + n + 1,com1);
63     Divide (1,n);
64     for (I i(1);i <= n; ++ i)
65         Max (ans,f[i] - (n - i + 1) * (n - i) / 2);
66     Max (ans,-(n + 1) * n / 2);
67     printf ("%lld\n",ans);
68 }

View Code