# 1. 题目

add a b c：把区间 [a,b] 内的所有数都增加 c

set a b c：把区间 [a,b] 内的所有数都设为 c

sum a b：查询区间 [a,b] 的区间和

max a b：查询区间 [a,b] 的最大值

min a b：查询区间 [a,b] 的最小值

# 2. 题解

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct N
{
LL l,r,sum,max,min,pf,cf;bool book;N*s[2];
N(){l=r=sum=max=min=pf=cf=book=0,s[0]=s[1]=0;}
}*root=0;
void update(N*&a)
{
a->sum=a->s[0]->sum+a->s[1]->sum;
a->max=max(a->s[0]->max,a->s[1]->max);
a->min=min(a->s[0]->min,a->s[1]->min);
}
void pdown(N*&a)
{
if(a->book)
{
a->s[0]->sum=(a->s[0]->r-a->s[0]->l+1)*a->cf;
a->s[1]->sum=(a->s[1]->r-a->s[1]->l+1)*a->cf;
a->s[0]->max=a->s[0]->min=a->s[1]->max=a->s[1]->min=a->cf;
a->s[0]->cf=a->s[1]->cf=a->cf,a->s[0]->pf=a->s[1]->pf=0;
a->s[0]->book=a->s[1]->book=1;
}
else
{
a->s[0]->sum+=(a->s[0]->r-a->s[0]->l+1)*a->pf;
a->s[1]->sum+=(a->s[1]->r-a->s[1]->l+1)*a->pf;
a->s[0]->max+=a->pf,a->s[0]->min+=a->pf;
a->s[1]->max+=a->pf,a->s[1]->min+=a->pf;
if(a->s[0]->cf)a->s[0]->cf+=a->pf;else a->s[0]->pf+=a->pf;
if(a->s[1]->cf)a->s[1]->cf+=a->pf;else a->s[1]->pf+=a->pf;
}
a->cf=a->pf=a->book=0;
}
void build(LL l,LL r,N*&a)
{
a=new N,a->l=l,a->r=r;
if(l==r){scanf("%lld",&a->sum),a->max=a->min=a->sum;return;}
build(l,(l+r)>>1,a->s[0]),build(((l+r)>>1)+1,r,a->s[1]),update(a);
}
{
if(l<=a->l&&a->r<=r)
{
a->sum+=(a->r-a->l+1)*k,a->min+=k,a->max+=k;
if(a->book)a->cf+=k;else a->pf+=k;
return;
}
if(a->book||a->pf)pdown(a);
update(a);
}
void change(LL l,LL r,LL k,N*&a)
{
if(l<=a->l&&a->r<=r)
{a->sum=(a->r-a->l+1)*k,a->min=k,a->max=k,a->pf=0,a->cf=k,a->book=1;return;}
if(a->book||a->pf)pdown(a);
if(l<=((a->l+a->r)>>1))change(l,r,k,a->s[0]);
if(r>((a->l+a->r)>>1))change(l,r,k,a->s[1]);
update(a);
}
LL query_sum(LL l,LL r,N*&a)
{
if(l<=a->l&&a->r<=r)return a->sum;
if(a->book||a->pf)pdown(a);
LL tot=0;
if(l<=((a->l+a->r)>>1))tot+=query_sum(l,r,a->s[0]);
if(r>((a->l+a->r)>>1))tot+=query_sum(l,r,a->s[1]);
}
LL query_min(LL l,LL r,N*&a)
{
if(l<=a->l&&a->r<=r)return a->min;
if(a->book||a->pf)pdown(a);
LL tot=LLONG_MAX;
if(l<=((a->l+a->r)>>1))tot=min(tot,query_min(l,r,a->s[0]));
if(r>((a->l+a->r)>>1))tot=min(tot,query_min(l,r,a->s[1]));
}
LL query_max(LL l,LL r,N*&a)
{
if(l<=a->l&&a->r<=r)return a->max;
if(a->book||a->pf)pdown(a);
LL tot=LLONG_MIN;
if(l<=((a->l+a->r)>>1))tot=max(tot,query_max(l,r,a->s[0]));
if(r>((a->l+a->r)>>1))tot=max(tot,query_max(l,r,a->s[1]));
}
LL n,m;
char opt[10];
int main()
{
scanf("%lld%lld",&n,&m),build(1,n,root);
for(LL i=1,a,b,c;i<=m;i++)
{
scanf("%s%lld%lld",opt,&a,&b);
else if(!strcmp(opt,"set"))scanf("%lld",&c),change(a,b,c,root);
else if(!strcmp(opt,"sum"))printf("%lld\n",query_sum(a,b,root));
else if(!strcmp(opt,"min"))printf("%lld\n",query_min(a,b,root));
else printf("%lld\n",query_max(a,b,root));
}
return 0;
}