RT，可以看前面一个贴了说了 m 是 2e6，但题目写成了 1e6。

同时求卡常 （T on 11~18,20,31,35,38,40）qaq

#include<bits/stdc++.h>
using namespace std;

const int N=1000000;
int n,m,x,c,a[N+5];
long long z[N+5],qad[N+5],f[N+5],g[N+5],cnt,ha,he;//size should be bigger
#define max(a,b) (((a)>(b))?(a):(b))
#define mid (l+r>>1)
#define midd (tr[x].l+tr[x].r>>1)
#define middd (tr2[x].l+tr2[x].r>>1)
#define ls (x<<1)
#define rs (x<<1|1)
#define ll long long
const ll INF=1e18;
#define SIZE (1<<24)
char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(p3=out,1,SIZE,stdout))
#define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
class Flush{public:~Flush(){flush();}}_;   
template<typename type>
inline void rd(type &x)
{
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void wr(type x)
{
static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10;while(x);
while(top) putchar(Stack[top--]|48);
putchar('\n');
}
namespace seg1{//块内
  struct no{
  ll lm,rm,ans,l,r,sum;
  }tr[N*4+5];
  no inline hb(const no &a,const no &b){
  no c;c.lm=max(a.lm,a.sum+b.lm);
  c.rm=max(b.rm,b.sum+a.rm);
  c.sum=a.sum+b.sum;
  c.ans=max(a.ans,max(b.ans,a.rm+b.lm));
  c.l=a.l,c.r=b.r;
  return c;
  }
  void inline build(int x,int l,int r){
  tr[x].l=l,tr[x].r=r;
  if(l==r){tr[x].lm=tr[x].rm=tr[x].ans=tr[x].sum=a[l];return ;}
  build(ls,l,mid);
  build(rs,mid+1,r);
  tr[x]=hb(tr[ls],tr[rs]);
  }
  void inline xg(int x,int y,int z){
  if(tr[x].l==tr[x].r){tr[x].lm=tr[x].rm=tr[x].ans=tr[x].sum=z;return ;}
  if(y<=midd)xg(ls,y,z);
  else xg(rs,y,z);
  tr[x]=hb(tr[ls],tr[rs]);
  }
  no inline ask(int x,int l,int r){
  if(l<=tr[x].l&&r>=tr[x].r)return tr[x];
  if(l<=midd&&r>midd)return hb(ask(ls,l,r),ask(rs,l,r));
  if(l<=midd)return ask(ls,l,r);
  return ask(rs,l,r);
  }
}
namespace seg2{//块内max&相邻max
  struct no{
  ll mx,l,r;
  }tr[N*4+5];
  struct no2{
  ll mx,l,r;
  }tr2[N*4+5];
  no inline hb(const no &a,const no &b){
  no c;c.mx=max(a.mx,b.mx);
  c.l=a.l,c.r=b.r;
  return c;
  }
  no2 inline hb2(const no2 &a,const no2 &b){
  no2 c;c.mx=max(a.mx,b.mx);
  c.l=a.l,c.r=b.r;
  return c;
  }
  void inline build(int x,int l,int r){
  tr[x].l=l,tr[x].r=r;
  if(l==r){tr[x].mx=z[l];return ;}
  build(ls,l,mid);
  build(rs,mid+1,r);
  tr[x]=hb(tr[ls],tr[rs]);
  }
  void inline build2(int x,int l,int r){
  tr2[x].l=l,tr2[x].r=r;
  if(l==r){tr2[x].mx=qad[l];return ;}
  build2(ls,l,mid);
  build2(rs,mid+1,r);
  tr2[x]=hb2(tr2[ls],tr2[rs]);
  }
  void inline xg(int x,int y,int z){
  if(tr[x].l==tr[x].r){tr[x].mx=z;return ;}
  if(y<=midd)xg(ls,y,z);
  else xg(rs,y,z);
  tr[x]=hb(tr[ls],tr[rs]);
  }
  void inline xg2(int x,int y,int z){
  if(tr2[x].l==tr2[x].r){tr2[x].mx=z;return ;}
  if(y<=middd)xg2(ls,y,z);
  else xg2(rs,y,z);
  tr2[x]=hb2(tr2[ls],tr2[rs]);
  }
  no inline ask(int x,int l,int r){
  if(l<=tr[x].l&&r>=tr[x].r)return tr[x];
  if(l<=midd&&r>midd)return hb(ask(ls,l,r),ask(rs,l,r));
  if(l<=midd)return ask(ls,l,r);
  return ask(rs,l,r);
  }
  no2 inline ask2(int x,int l,int r){
  if(l<=tr2[x].l&&r>=tr2[x].r)return tr2[x];
  if(l<=middd&&r>middd)return hb2(ask2(ls,l,r),ask2(rs,l,r));
  if(l<=middd)return ask2(ls,l,r);
  return ask2(rs,l,r);
  }
}
struct seg3{
   struct no{
  ll lm,rm,ans,l,r,laz1,laz2;
  };
  vector<no>tr;
  void inline push_down(int x){
  if(tr[x].laz1){//cout<<"lsm666";
  tr[ls].laz1+=tr[x].laz1,tr[rs].laz1+=tr[x].laz1;
  tr[ls].ans+=tr[x].laz1;tr[rs].ans+=tr[x].laz1;
  tr[ls].lm+=tr[x].laz1;tr[rs].lm+=tr[x].laz1;
  tr[x].laz1=0;
  }
  if(tr[x].laz2){//cout<<"zzl666";
  tr[ls].laz2+=tr[x].laz2,tr[rs].laz2+=tr[x].laz2;
  tr[ls].ans+=tr[x].laz2;tr[rs].ans+=tr[x].laz2;
  tr[ls].rm+=tr[x].laz2;tr[rs].rm+=tr[x].laz2;
  tr[x].laz2=0;
  }
  }
  no inline hb(const no &a,const no &b){
  no c;c.lm=max(a.lm,b.lm);
  c.rm=max(a.rm,b.rm);
  c.ans=max(a.ans,max(b.ans,a.lm+b.rm));
  c.r=a.r,c.l=b.l;
  c.laz1=c.laz2=0;
 // cout<<a.lm<<" "<<a.rm<<" "<<a.l<<" "<<a.r<<" "<<b.l<<" "<<b.lm<<" "<<b.rm<<" "<<b.r;
  return c;
  }
  void inline build(int x,int l,int r){
  tr[x].l=l,tr[x].r=r;tr[x].laz1=tr[x].laz2=0;
  if(l==r){tr[x].laz1=tr[x].laz2=0;tr[x].lm=g[l];tr[x].rm=f[l];tr[x].ans=-INF;return ;}
  build(ls,l,mid);
  build(rs,mid+1,r);
  tr[x]=hb(tr[rs],tr[ls]);
  }
  void inline xg(int x,int l,int r,int z){
  if(tr[x].l>=l&&tr[x].r<=r){/*cout<<x<<" "<<tr[x].l<<" "<<tr[x].r<<" guosha"<<z<<endl;*/tr[x].lm+=z;tr[x].laz1+=z;tr[x].ans+=z;return ;}
  push_down(x);
  if(l<=midd)xg(ls,l,r,z);
  if(r>midd)xg(rs,l,r,z);
  tr[x]=hb(tr[rs],tr[ls]);
  }
  void inline xg2(int x,int l,int r,int z){
  if(tr[x].l>=l&&tr[x].r<=r){/*cout<<x<<" "<<tr[x].l<<" "<<tr[x].r<<" guosha"<<z<<endl;*/tr[x].rm+=z;tr[x].laz2+=z;tr[x].ans+=z;return ;}
  push_down(x);
  if(l<=midd)xg2(ls,l,r,z);
  if(r>midd)xg2(rs,l,r,z);
  tr[x]=hb(tr[rs],tr[ls]);
  }
  no inline ask(int x,int l,int r){
  if(l>r)return no{0,0,0,0,0,0,0};
  if(l<=tr[x].l&&r>=tr[x].r){/*cout<<x<<" "<<tr[x].l<<" "<<tr[x].r<<" "<<tr[x].lm<<" "<<tr[x].rm<<"iopirope\n";*/return tr[x];}
  push_down(x);
  if(l<=midd&&r>midd)return hb(ask(rs,l,r),ask(ls,l,r));
  if(l<=midd)return ask(ls,l,r);
  return ask(rs,l,r);
  }
}tr[N+5];
signed main(){
  int l=0,r=0,ks=0,opt=0;
  rd(n);rd(m);rd(c);
  for(int i=1;i<=n;i++){rd(a[i]);}
  ks=(n+c-1)/c;
  seg1::build(1,1,n);
  if(ks==1){
     while(m--){
     rd(opt);rd(l);rd(r);
     if(opt==1)seg1::xg(1,l,r);
     else cout<<max((long long)0,seg1::ask(1,l,r).ans)<<"\n";
     }    
     return 0;
  }
  if(c==1){
  for(int i=1;i<=n;i++)z[i]=a[i];
  seg2::build(1,1,n);
  while(m--){
  rd(opt);rd(l);rd(r);
  if(opt==1)seg2::xg(1,l,r);
  else cout<<max((long long)0,seg2::ask(1,l,r).mx)<<"\n";
  
  }return 0;
  }
  for(int i=1;i<ks;i++)tr[i].tr.resize(c<<2);//cout<<"h"<<endl;
  for(int i=1;i<=ks;i++)z[i]=seg1::ask(1,(i-1)*c+1,min(n,i*c)).ans;//cout<<"e"<<endl;
  seg2::build(1,1,ks);//cout<<"l"<<endl;
  for(int i=1;i<=n;i++)g[i]=a[i];//cout<<"l"<<endl;
  for(int i=1;i<=n-c;i++)f[i]=a[i+c];//cout<<"o"<<endl;
  for(int i=n-c+1;i<=n;i++)f[i]=-1e10;//cout<<"w";
  for(int i=1;i<=ks-1;i++){
  for(int j=(i*c)-1;j>=(i-1)*c+1;j--)
  g[j]+=g[j+1];//cout<<"o"<<endl;
  for(int j=(i-1)*c+2;j<=(i)*c;j++)
  f[j]+=f[j-1];//cout<<"r"<<endl;
  tr[i].build(1,(i-1)*c+1,i*c);//cout<<"l"<<endl;
  qad[i]=tr[i].ask(1,(i-1)*c+1,i*c).ans;//cout<<"d"<<endl;
 // cout<<i<<" "<<qad[i]<<endl;
  }
 // cout<<"6"<<endl;
  seg2::build2(1,1,ks-1);
 // cout<<tr[1].tr[3].lm<<"OP"<<endl;
  while(m--){
  rd(opt);rd(l);rd(r);
  if(opt==1){
  seg1::xg(1,l,r);
  int noww=(l+c-1)/c;
  z[noww]=seg1::ask(1,(noww-1)*c+1,min(noww*c,n)).ans;
  seg2::xg(1,noww,z[noww]);
  if(noww!=1){
  int gd=r-a[l];

  tr[noww-1].xg2(1,l-c,(noww-1)*c,gd);
  qad[noww-1]=tr[noww-1].ask(1,(noww-2)*c+1,(noww-1)*c).ans;
  seg2::xg2(1,noww-1,qad[noww-1]);
  }
  if(noww!=ks){
  int gd=r-a[l];

  tr[noww].xg(1,(noww-1)*c+1,l,gd);
  qad[noww]=tr[noww].ask(1,(noww-1)*c+1,noww*c).ans;
  seg2::xg2(1,noww,qad[noww]);
  }
  a[l]=r;
  }
  else{
  int nowl=(l+c-1)/c,nowr=(r+c-1)/c;
  long long ans=0;
  if(nowr-nowl>1){ha=seg2::ask(1,nowl+1,nowr-1).mx;ans=max(ans,ha);}
  if(nowr-nowl>2){he=seg2::ask2(1,nowl+1,nowr-2).mx;ans=max(ans,he);}
  if(r-l+1<=c){ha=seg1::ask(1,l,r).ans;wr(max((long long)0,ha));continue;}
  if(nowr-nowl==1){
  ha=tr[nowl].ask(1,l,nowl*c).lm,he=tr[nowl].ask(1,(nowl-1)*c+1,l-1).rm;
  ans=max(ans,max((long long)0,ha)+max((long long)0,he));//cout<<ans<<endl;
  ha=tr[nowl].ask(1,r-c+1,nowl*c).lm,he=tr[nowl].ask(1,(nowl-1)*c+1,r-c).rm;
  ans=max(ans,max((long long)0,ha)+max((long long)0,he));//cout<<ans<<endl;//" "<<tr[nowl].ask(1,3,4)<<endl;
  ha=seg1::ask(1,l,l+c-1).ans,he=seg1::ask(1,r-c+1,r).ans;
  ans=max(ans,max(ha,he));//cout<<ans<<endl;
  ha=tr[nowl].ask(1,l,r-c).ans;
  ans=max(ans,ha);//cout<<ans<<endl;
  }
  else{
  ha=tr[nowl].ask(1,l,nowl*c).lm,he=tr[nowl].ask(1,(nowl-1)*c+1,l-1).rm;
  ans=max(ans,max((long long)0,ha)+max((long long)0,he));
 // ans=max(ans,tr[nowl].ask(1,r-c+1,nowl*c).lm+tr[nowl].ask(1,(nowl-1)*c+1,r-c).rm);cout<<ans<<endl;
 ha=seg1::ask(1,l,l+c-1).ans;
  ans=max(ans,ha);//cout<<ans<<endl;
  ha=tr[nowl].ask(1,l,nowl*c).ans;
  ans=max(ans,ha);//cout<<ans<<endl;
ha=tr[nowr-1].ask(1,r-c+1,(nowr-1)*c).lm;
he=tr[nowr-1].ask(1,(nowr-2)*c+1,r-c).rm;
  //ans=max(ans,tr[nowr-1].ask(1,l,nowl*c).lm+tr[nowl].ask(1,(nowl-1)*c+1,l-1).rm);
  ans=max(ans,max((long long)0,ha)+max((long long)0,he));//cout<<ans<<endl;
  ha=seg1::ask(1,r-c+1,r).ans;
  ans=max(ans,ha);
  ha=tr[nowr-1].ask(1,(nowr-2)*c+1,r-c).ans;
  ans=max(ans,ha);//cout<<ans<<endl;
  }
  wr(ans);
  }
  }
}//cout<<ans<<" "<<tr[nowl].ask(1,l+1,nowl*c).lm<<" "<<tr[nowl+1].ask(1,nowl*c+1,l+c).rm<<l+1<<" "<<nowl*c<<" "<<endl;