考虑分块，每块维护两个标记$ts,td$。

那么对于块中一个位置$i$，它的实际值为$i\times td+ts+v_i$。

修改的时候，对于整块，直接打标记，对于零散的暴力修改，然后重构凸壳，时间复杂度$O(\sqrt{n})$。

查询的时候在凸壳上二分即可，时间复杂度$O(\sqrt{n}\log n)$。

 

#include
     
      #define N 100010typedef long long ll;int n,m,cnt,lim,i,op,x,y,pos[N],st[N],en[N],R[N],q[N];ll v[N],ts[N],td[N];inline int read(){  char c;bool f=0;int a=0;  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));  if(c!='-')a=c-'0';else f=1;  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';  if(f)a=-a;  return a;}inline double cross(int x,int y){return(double)(v[x]-v[y])/(double)(y-x);}inline void build(int x){  int i,L=st[x],t=L;  q[t]=t;  for(i=t+1;i<=en[x];q[++t]=i++)while(t>L&&cross(i,q[t])<=cross(q[t],q[t-1]))t--;  R[x]=t;}inline void change(int x,int y,ll s,ll d){  if(pos[x]==pos[y]){    for(int i=x;i<=y;i++)v[i]+=s+d*i;    build(pos[x]);    return;  }  for(int i=pos[x]+1;i
      
       =x;i--)v[i]+=s+d*i;  build(pos[x]);  for(int i=st[pos[y]];i<=y;i++)v[i]+=s+d*i;  build(pos[y]);}inline void modify(int x,int y,ll z){  change(x,y,z*(1-x),z);  if(y
       
        >1;    if(cross(q[mid-1],q[mid])
        
         =x;i--)up(t,td[pos[i]]*i+ts[pos[i]]+v[i]);  for(int i=st[pos[y]];i<=y;i++)up(t,td[pos[i]]*i+ts[pos[i]]+v[i]);  return t;}int main(){  n=read();  for(i=1;i<=n;i++)v[i]=v[i-1]+read();  while(lim*lim*8