T2：Function

看到题目里的递推式，莫名其妙先画了个网格，横x轴纵y轴。

然后发现第一排是a1的各个倍数，第一列是ai自己。然后根据相邻两个a的大小关系好像可以推路径。

然后写暴力打了个表，按普通的行列输出，发现自己这部分想麻烦了。似乎前面小的ai可以斜着连过来覆盖现在的ai，一列会分段被多个ai覆盖。然后感觉有点像决策单调性【什么】，试图从前面转移。

然后考虑给一列打标记，在哪个x开始被前面的哪个a覆盖，然后每一列从上一列转移这个标记。然后发现中间有断层，行不通。

这个时候重新开始想之前发现的斜着连过来这一块，一个（x，y）可以先向之前的ai的列去走，然后到某一列一直走到顶。

于是怎么找这个ai？

把走到ai这列得出的答案列了个式子：ai*（x-y）+s[y]-s[i]+i*a[i]。假设从（x，y）往回一直走到第一列，还剩下x-y步到顶，这部分一定要填ai。然而ai不一定是第一列，多往回走几列就少让ai累加了多少行，再把这部分补上。以及第一行就是ai本身而不是从0开始所以相当于ai多累加一行。

对于一个询问，sy是不变的，所以先去掉。发现剩下的这部分式子是一个关于x-y的一次函数。假设a=ai，b=-s[i]+i*a[i]。

我对斜率优化不熟…在这里开始懵逼了，最后强行头铁出了单调栈这一步但是写不完了。

推出一次函数以后，考虑ai比aj优的条件。两个式子用不等式算一下得出i比j优的条件是（bj-bi）/（ai-aj）>（x-y），两个ai覆盖的交点也可以这样得到。

维护一个下凸包，斜率递增。

观察打好的表发现，覆盖同一列y的ai从靠近y的地方递减。离y远而a更大的ai没有再做贡献的可能性，即作贡献的ai递减。

所以可以用单调栈维护。询问的时候在凸壳上二分x的位置。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,q,cnt=1;
long long a[1000010],sum[1000010],b[1000010],ans[1000010];
double num[1000010];
int t[1000010],p;
struct node{
    int x,y,id;
}que[1000010];
bool cmp(node a,node b){
    if(a.y==b.y)return a.x<b.x;
    else return a.y<b.y;
}
double get(int x,int y){
    return (double)(b[y]-b[x])/(double)(a[x]-a[y]);
}
int main()
{
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
        b[i]=i*a[i]-sum[i];
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&que[i].x,&que[i].y);
        que[i].id=i;
    }
    sort(que+1,que+q+1,cmp);
    for(int i=1;i<=n;i++){
        while(p&&a[t[p]]>=a[i])p--;
        while(p>=2&&get(i,t[p])>get(t[p],t[p-1]))p--;
        t[++p]=i;
        if(p>1)num[n-p]=get(i,t[p-1]);
        while(que[cnt].y==i){
            int x=lower_bound(num+n-p,num+n-1,(que[cnt].x-que[cnt].y))-num;
            x=n-x;
            ans[que[cnt].id]=a[t[x]]*(que[cnt].x-que[cnt].y)+b[t[x]]+sum[que[cnt].y];
            cnt++;
        }
    }
    for(int i=1;i<=q;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

View Code

有些地方自己也不是很明白，再找一点斜率优化的题写…