C++ 解法, 执行用时: 61ms, 内存消耗: 7160K, 提交时间: 2021-05-22 17:23:10

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
pair<long long,long long>que[MAXN];///<pos,val>
int head,tail,n,m;
struct node
{
    int id;
    long long a,k;
}query[MAXN];
long long ans[MAXN],a[MAXN];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%lld %lld",&query[i].a,&query[i].k);
        query[i].id=i;
    }
    sort(query+1,query+1+m,[](const node&A,const node&B){
         return A.k>B.k;
    });
    for(int i=1;i<=n;++i)
    {
        while(tail>=2&&(a[i]-que[tail].second)*(i-que[tail-1].first)>(a[i]-que[tail-1].second)*(i-que[tail].first))tail--;
        que[++tail]=make_pair(i,a[i]);
    }
    head=1;
    for(int i=1;i<=m;++i)
    {
        while(head<tail&&(que[head].first-1)*query[i].k-que[head].second>=(que[head+1].first-1)*query[i].k-que[head+1].second)head++;
        ans[query[i].id]=query[i].a+(que[head].first-1)*query[i].k-que[head].second;
    }
    for(int i=1;i<=m;++i)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}