Serega and Fedor play with functions. One day they came across a very interesting function. It looks like that:
- f(1,?j)?=?a[j], 1?≤?j?≤?n.
- f(i,?j)?=?min(f(i?-?1,?j),?f(i?-?1,?j?-?1))?+?a[j], 2?≤?i?≤?n, i?≤?j?≤?n.
Here a is an integer array of length n.
Serega and Fedya want to know what values this function takes at some points. But they don't want to calculate the values manually. So they ask you to help them.
The first line contains integer n (1?≤?n?≤?105) — the length of array a. The next line contains n integers: a[1],?a[2],?...,?a[n](0?≤?a[i]?≤?104).
The next line contains integer m (1?≤?m?≤?105) — the number of queries. Each of the next m lines contains two integers: xi, yi (1?≤?xi?≤?yi?≤?n). Each line means that Fedor and Serega want to know the value of f(xi,?yi).
Print m lines — the answers to the guys' queries.
6 2 2 3 4 3 4 4 4 5 3 4 3 4 2 3
12 9 9 5
7 1 3 2 3 4 0 2 4 4 5 2 3 1 4 4 6
11 4 3 0
斜率优化+二分+思路~
我们发现题目里面f相当于是一个DP式子，求的是(1,s)到(x,y)路径的最短距离，通过绘图可以发现，答案就是选择一个s使得a[s]最小，ans=(x-y+s)*a[s]+c[y]-c[s]，化简得c[hy]-c[s]+a[s]*s+(x-y)*a[s]，其中c[]为a[]的前缀和。
这样，我们就可以用斜率优化辣！
每个点为(a[s],-c[s]+a[s]*s)，用单调栈维护，每次二分查找即可~
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define cal(i,j) (-c[i]+(double)a[i]*i+c[j]-(double)a[j]*j)/(a[i]-a[j])int n,m,x,y,a[100001],c[100001],ans[100001],sta[100001],top;struct node{int x,y,id;bool operator < (const node&u) {return y<u.y;}
}q[100001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int find(int u)
{int l=1,r=top,mid,ans;while(l<=r){mid=l+r>>1;if(sta[mid]>u) ans=mid,r=mid-1;else l=mid+1;}return ans;
}int main()
{n=read();for(int i=1;i<=n;i++) a[i]=read(),c[i]=c[i-1]+a[i];m=read();for(int i=1;i<=m;i++) q[i].x=read(),q[i].y=read(),q[i].id=i;sort(q+1,q+m+1);for(int i=1,j=1;i<=n;i++){while(top>0 && a[sta[top]]>=a[i]) top--;while(top>1 && cal(sta[top],i)<=cal(sta[top-1],i)) top--;sta[++top]=i;while(j<=m && q[j].y==i){int l=find(i-q[j].x),r=top-1,mid,now=i;while(l<=r){mid=l+r>>1;if(cal(sta[mid],sta[mid+1])>=i-q[j].x) now=sta[mid],r=mid-1;else l=mid+1;}ans[q[j].id]=c[i]-c[now]+a[now]*(q[j].x-i+now);j++;} }for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}