引用：这是一道非常棒的思维题，可以说没有用到任何高深的知识点，却极大地考验了做题人的思维能力和创造性。
本题分为两步。
-
根据线性规划对偶或贪心，转化题意。
-
对 \(m\) 根号分治，然后分别进行分治。
\(m\le \sqrt{n}\)分治比较好想，\(m>\sqrt{n}\) 的根号分治比较难想。
这两种分治的细节都很多，调了一整天
原题还卡常，无语了
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
int n,m,q,qt,B;
ll a[N*2],b[N],c[N],ans[N],sum[N];
struct ques{
int l,r,id;
}o[N];
namespace ST{
const int K=__lg(N)+2;
ll f[K][N];
void build(){
for(int i=1;i<=n;i++)f[0][i]=a[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);
}
ll query(int l,int r){
int k=__lg(r-l+1);
return max(f[k][l],f[k][r-(1<<k)+1]);
}
}
void reduce(){
qt=q,q=0;
for(int i=1;i<=qt;i++){
if(o[i].r-o[i].l+1>m)o[++q]=o[i];
else if(o[i].l<=o[i].r)
ans[i]=max(ans[i],ST::query(o[i].l,o[i].r));
}
}
namespace Solve1{
ll f[N],g[N];
void solve(int l,int r,vector<ques>o){
if(o.empty()||r-l+1<=m)return;
vector<ques>L,R,T;
int mid=(l+r)>>1;
for(ques x:o){
if(x.r<=mid)L.push_back(x);
else if(mid<x.l)R.push_back(x);
else T.push_back(x);
}
solve(l,mid,L),solve(mid+1,r,R);
if(T.empty())return;
// for(int i=73;i<=93;i++)printf("%lld%c",a[i],"\n "[i<93]);
for(int d=0;d<=m;d++){
int L=mid-d+1,R=L+m-2;
L=max(L,l),R=min(R,r);
for(int i=L;i<=mid;i++)f[i]=0;
for(int i=R;i>mid;i--)g[i]=0;
f[L]=g[R]=0;
for(int i=L-1;i>=l;i--){
f[i]=max(f[i+1],(i+m<L?f[i+m]:0)+a[i]);
}
for(int i=R+1;i<=r;i++){
g[i]=max(g[i-1],(i-m>R?g[i-m]:0)+a[i]);
}
for(ques x:T)ans[x.id]=max(ans[x.id],f[x.l]+g[x.r]);
}
}
void solve(){
solve(1,n,{o+1,o+1+q});
}
}
namespace Solve2{
#define id(x,y) ((y)*m+(x))
const int S=sqrt(N)+5,M=N*2;
int h,b[M];
struct ques{
int a,b,x,y,id;
};
ll sum[S],c[M],f[M],g[M];
int k,gap;
void solve(int l,int r,vector<ques>o){
if(o.empty())return;
if(l==r){
for(int i=0;i<h;i++)sum[i]=(i?sum[i-1]:0)+a[id(l,i)];
for(ques x:o)ans[x.id]=max(ans[x.id],sum[x.x]-(x.a?sum[x.a-1]:0));
return;
}
int mid=(l+r)>>1;
vector<ques>L,R;
for(ques x:o)if(x.b<=x.y){
if(x.b<=mid&&x.y<=mid)L.push_back(x);
else if(mid<x.b&&mid<x.y)R.push_back(x);
}
solve(l,mid,L),solve(mid+1,r,R);
gap=r-l+1,k=0;
for(int i=0;i<h;i++)for(int j=l;j<=r;j++){
b[id(j,i)]=++k,c[k]=a[id(j,i)];
}
for(int l=1-gap,r=0,i=0;i<=h+1;l+=gap,r+=gap,i++){
for(int j=min(l-1,k);j>=1;j--)f[j]=max(f[j+1],(j+gap<=k?f[j+gap]:0)+c[j]);
for(int j=max(r+1,1);j<=k;j++)g[j]=max(g[j-1],(j>gap?g[j-gap]:0)+c[j]);
for(ques x:o)if(b[id(x.b,x.a)]<=r&&b[id(x.y,x.x)]>=l){
ans[x.id]=max(ans[x.id],f[b[id(x.b,x.a)]]+g[b[id(x.y,x.x)]]);
}
for(int j=min(l-1,k);j>=1;j--)f[j]=0;
for(int j=max(r+1,1);j<=k;j++)g[j]=0;
}
for(int r=(gap+1)/2,l=r-gap+1,i=0;i<=h;l+=gap,r+=gap,i++){
for(int j=min(l-1,k);j>=1;j--)f[j]=max(f[j+1],(j+gap<=k?f[j+gap]:0)+c[j]);
for(int j=max(r+1,1);j<=k;j++)g[j]=max(g[j-1],(j>gap?g[j-gap]:0)+c[j]);
for(ques x:o)if(b[id(x.b,x.a)]<=r&&b[id(x.y,x.x)]>=l){
ans[x.id]=max(ans[x.id],f[b[id(x.b,x.a)]]+g[b[id(x.y,x.x)]]);
}
for(int j=min(l-1,k);j>=1;j--)f[j]=0;
for(int j=max(r+1,1);j<=k;j++)g[j]=0;
}
// cerr<<l<<' '<<r<<' '<<ans[1]<<endl;
}
void solve(){
h=(n-1)/m+1;
vector<ques>o(q);
for(int i=0;i<q;i++){
o[i].a=::o[i+1].l/m;
o[i].b=::o[i+1].l%m;
o[i].x=::o[i+1].r/m;
o[i].y=::o[i+1].r%m;
o[i].id=::o[i+1].id;
}
solve(0,m-1,o);
}
}
int main(){
freopen("snow.in","r",stdin);
freopen("snow.out","w",stdout);
scanf("%d%d%d",&n,&m,&q),B=sqrt(n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++)if(a[i]>a[i+1]){
b[i]=a[i]-a[i+1];
c[max(i-m+1,1)]-=b[i],c[i+1]+=b[i];
}
for(int i=1;i<=n;i++)b[i]+=b[i-1],c[i]+=c[i-1];
for(int i=1;i<=q;i++){
scanf("%d%d",&o[i].l,&o[i].r),o[i].id=i;
// for(int j=o[i].l;j<=o[i].r;j++)printf("%lld%c",a[j],"\n "[j<o[i].r]);
sum[i]=b[o[i].r-1]-b[o[i].l-1]+a[o[i].r];
o[i].r-=m;
}
for(int i=1;i<=n;i++)a[i]=max(a[i]+c[i],0ll);
ST::build();
reduce();
if(m<=B)Solve1::solve();
else Solve2::solve();
for(int i=1;i<=qt;i++)printf("%lld\n",ans[i]+sum[i]);
return 0;
}