吉司机课件题。
区间min,区间最值，区间和。
如果用最大值和次大值能更新区间和那就更新打标记，否则暴力dfs。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
#define N 500005
#define LL long long
#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
using namespace std;
int n,m;
int as[N];
struct node
{
LL sum;
int mx,num,se;
int lazy;
}a[N*];
inline int read()
{
int p=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')p=p*+c-'',c=getchar();
return p;
}
void push_up(int x)
{
int l=x<<,r=x<<|;
a[x].mx=a[l].mx;a[x].num=a[l].num;a[x].se=a[l].se;a[x].sum=a[l].sum+a[r].sum;
if(a[r].mx==a[x].mx)a[x].num+=a[r].num,a[x].se=max(a[x].se,a[r].se);
else if(a[r].mx<a[x].mx)a[x].se=max(a[x].se,a[r].mx);
else
{
a[x].se=max(a[x].mx,a[r].se);
a[x].mx=a[r].mx;
a[x].num=a[r].num;
}
return ;
}
void push_down(int x)
{
a[x].lazy=;
int l=x<<,r=x<<|,val=a[x].mx;
if(a[l].mx>val)
{
a[l].sum-=1LL*a[l].num*(a[l].mx-val);
a[l].lazy=;a[l].mx=val;
}
if(a[r].mx>val)
{
a[r].sum-=1LL*a[r].num*(a[r].mx-val);
a[r].lazy=;a[r].mx=val;
}
}
void build(int x,int l,int r)
{
a[x].se=-;
a[x].lazy=;
if(l==r)
{
a[x].num=;
a[x].mx=as[l];
a[x].sum=as[l];
return ;
}
int mid=(l+r)>>;
build(ls);
build(rs);
push_up(x);
}
int qurmx(int x,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr)
{
return a[x].mx;
}
if(a[x].lazy)push_down(x);
int mid=(l+r)>>;
if(ll>mid)return qurmx(rs,ll,rr);
if(rr<=mid)return qurmx(ls,ll,rr);
return max(qurmx(ls,ll,rr),qurmx(rs,ll,rr));
}
LL qursum(int x,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr)
{
return a[x].sum;
}
if(a[x].lazy)push_down(x);
int mid=(l+r)>>;
if(ll>mid)return qursum(rs,ll,rr);
if(rr<=mid)return qursum(ls,ll,rr);
return qursum(ls,ll,rr)+qursum(rs,ll,rr);
}
void gai(int x,int l,int r,int ll,int rr,int z)
{
if(z>=a[x].mx)return ;
if(l>=ll&&r<=rr)
{
if(z>a[x].se)
{
a[x].lazy=;
a[x].sum-=1LL*a[x].num*(a[x].mx-z);
a[x].mx=z;return ;
}
}
if(a[x].lazy)push_down(x);
int mid=(l+r)>>;
if(ll<=mid)gai(ls,ll,rr,z);
if(rr>mid)gai(rs,ll,rr,z);
push_up(x);
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)as[i]=read();
build(,,n);int op,t1,t2,t3;
for(int i=;i<=m;i++)
{
op=read();
if(op==)
{
t1=read();t2=read();t3=read();
gai(,,n,t1,t2,t3);
}
else if(op==)
{
t1=read();t2=read();
printf("%d\n",qurmx(,,n,t1,t2));
}
else
{
t1=read();t2=read();
printf("%lld\n",qursum(,,n,t1,t2));
}
}
}
return ;
}