京都观光 的加强版😅

考虑怎么算贡献。首先还是求出 { c i } \{c_i\} {ci​}对应的凸包，然后对于每个$c_i$，我们可以二分求出其被插入到了第$j$行的后面，记这一行为$p_i$，$c_i$对应第$y_i$列，$p_m=x$，那么答案是:

$$\sum _{i=1}^{m-1}{c}_i(p_{i+1}-p_i)+\sum _{i=2}^{m-1}{p}_i^2(y_i-y_{i-1})$$

这样，我们将询问离线下来，处理出单调栈中前缀和对应的答案，二分出这段前缀即可。

复杂度$O(q\log m)$。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
int n,m,Q;
int cnt,s[N];
ll c[N],res[N],sm[N],p[N];
vector<pair<int,int>>q[N];
ll calc(pair<ll,ll>x,pair<ll,ll>y){return x.fi*y.se-x.se*y.fi;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++)cin>>c[i];cin>>Q;for(int i=1;i<=Q;i++){int x,y;cin>>x>>y;q[y].pb({x,i});}p[1]=1;s[0]=1;for(int i=1;i<=m;i++){while(cnt>1&&calc({i-s[cnt],c[i]-c[s[cnt]]},{s[cnt]-s[cnt-1],c[s[cnt]]-c[s[cnt-1]]})>0)cnt--;s[++cnt]=i;if(cnt>1){p[cnt]=(1.0*(c[s[cnt]]-c[s[cnt-1]])/(s[cnt]-s[cnt-1])+1)/2;p[cnt]=max(p[cnt],1ll);sm[cnt]=sm[cnt-1]+c[s[cnt-1]]*(p[cnt]-p[cnt-1])+p[cnt-1]*p[cnt-1]*(s[cnt-1]-s[cnt-2]);}for(auto e:q[i]){ll x=e.fi;int id=e.se;if(cnt==1)res[id]=(x-1)*c[1];else{int l=1,r=cnt,tmp=0;while(l<=r){int mid=l+r>>1;if(p[mid]<=x)tmp=mid,l=mid+1;else r=mid-1;}res[id]=sm[tmp]+c[s[tmp]]*(x-p[tmp])+p[tmp]*p[tmp]*(s[tmp]-s[tmp-1])+(i-s[tmp])*x*x;}}}for(int i=1;i<=Q;i++)cout<<res[i]<<"\n";
}