rt，自己调了一天了，跟样例差1

站外题：

有 $n$ 场训练赛，第 $i$ 场的难度是 $a_i$，鲍勃可以从第 $1$ 场开始，依次考虑参加不参加。

他参加比赛的规则如下：

如果鲍勃同时参加了比赛 $i,j(j<i)$ 则应该有 $a[i]<=a[j]$。

如果鲍勃没有参加比赛 $i$, 并且这是连续第 $k$ 场没有参加的比赛，他将丢失 $k$ 点能力值。

鲍勃最终获得的能力值是所有参加的比赛的难度和减去丢失的能力值的和。

请你帮忙计算一下，鲍勃能获得的最大的能力值是多少？

$T$ 组数据，$n$ 的范围是 $10^5$。

dp式子是：

设 $f[i]$ 表示前 $i$ 场比赛，且第 $i$ 场比赛一定参加的最大值

则有：$f[i]=f[j]-\frac{(i-j-1)*(i-j)}{2}+a[i]$

然后我的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,T,f[N];
struct node{
	int num,id;
}a[N];
bool cmp1(node a,node b)
{
	return a.num<b.num;
}
bool cmp2(node a,node b)
{
	return a.id<b.id;
}
struct Point{
	int x,y;
	Point()
	{
		x=0,y=0;
	}
	Point(int a,int b)
	{
		x=a,y=b;
	}
}q[N];
double slope(Point i,Point j)
{
	return (double)((i.y-j.y)/(i.x-j.x));
}
void cdq(int l,int r)
{
	if(l==r)return;
	int mid=l+r>>1;
	cdq(l,mid);
	sort(a+l,a+mid+1,cmp2);
	sort(a+mid+1,a+r+1,cmp2);
	int l1=l,h=1,t=0;
	q[++t]=Point(0,0);
	for(int i=mid+1;i<=r;i++)
	{
		while(l1<=mid&&a[l1].id<a[i].id)
		{
			Point p=Point(-a[l1].id,f[a[l1].id]-(a[l1].id*a[l1].id+a[l1].id)/2);
			while(h<t&&slope(q[t],q[t-1])<=slope(q[t],p))t--;
			q[++t]=p;
			l1++;
		}
		while(h<t&&slope(q[h],q[h+1])<=a[i].id)h++;
		int j=-q[h].x;
		f[a[i].id]=f[j]-(a[i].id-j-1)*(a[i].id-j)/2+a[i].num;
	}
	sort(a+mid+1,a+r+1,cmp1);
	cdq(mid+1,r);
	return;
}
signed main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		cin>>a[i].num,a[i].id=i;
		sort(a+1,a+n+1,cmp1);
		memset(f,0,sizeof f);
		cdq(1,n);
		cout<<f[n]<<endl;
	}
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}