思路
学了个新科技叫势能线段树(又叫吉司机线段树)
好像是吉老师发明的XD
思路很简单,维护一个最大值max、严格次大值sec、最大值出现次数num、总和sum
然后操作1,2都是正常操作,操作0有几种特殊情况
第一种:c>=maxx,可以直接返回
第二种:c<maxx&&c>sec,只影响最大值,直接修改之后打上tag
第三种:c<=sec,没法讨论,直接递归到左右子节点继续修改之后上推信息
注意sum开longlong和所有涉及乘法的地方都要乘上一个1LL因为这个我WA了8次
时间复杂度好像是O(n\log^2 n)等我学会势能分析再证明复杂度
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct Node{
int maxx,sec,maxnum,tag;
long long sum;
}Seg[1000100<<2];
int a[1000100],n,m;
inline char Getchar() {
static char buf[2048], *p1 = buf, *p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,2048,stdin),p1==p2)?EOF:*p1++;
}
void pushup(int o){
if(Seg[o<<1].maxx>Seg[o<<1|1].maxx){
Seg[o].sum=Seg[o<<1].sum+Seg[o<<1|1].sum;
Seg[o].maxnum=Seg[o<<1].maxnum;
Seg[o].maxx=Seg[o<<1].maxx;
Seg[o].sec=max(Seg[o<<1|1].maxx,Seg[o<<1].sec);
}
else if(Seg[o<<1].maxx==Seg[o<<1|1].maxx){
Seg[o].sum=Seg[o<<1].sum+Seg[o<<1|1].sum;
Seg[o].maxnum=Seg[o<<1].maxnum+Seg[o<<1|1].maxnum;
Seg[o].maxx=Seg[o<<1].maxx;
Seg[o].sec=max(Seg[o<<1].sec,Seg[o<<1|1].sec);
}
else{//Seg[o<<1].maxx<Seg[o<<1|1].maxx
Seg[o].sum=Seg[o<<1].sum+Seg[o<<1|1].sum;
Seg[o].maxnum=Seg[o<<1|1].maxnum;
Seg[o].maxx=Seg[o<<1|1].maxx;
Seg[o].sec=max(Seg[o<<1].maxx,Seg[o<<1|1].sec);
}
}
void pushdown(int o){
if(Seg[o].tag!=-1){
if(Seg[o].tag<Seg[o<<1].maxx&&Seg[o<<1].sec<Seg[o].tag){
Seg[o<<1].sum-=(1LL*Seg[o<<1].maxx-Seg[o].tag)*Seg[o<<1].maxnum;
Seg[o<<1].maxx=Seg[o].tag;
Seg[o<<1].tag=Seg[o].tag;
}
if(Seg[o].tag<Seg[o<<1|1].maxx&&Seg[o<<1|1].sec<Seg[o].tag){
Seg[o<<1|1].sum-=(1LL*Seg[o<<1|1].maxx-Seg[o].tag)*Seg[o<<1|1].maxnum;
Seg[o<<1|1].maxx=Seg[o].tag;
Seg[o<<1|1].tag=Seg[o].tag;
}
Seg[o].tag=-1;
}
}
void build(int l,int r,int o){
Seg[o].tag=-1;
Seg[o].sum=0;
Seg[o].maxx=0;
Seg[o].sec=0;
Seg[o].maxnum=0;
if(l==r){
Seg[o].sum=a[l];
Seg[o].maxx=a[l];
Seg[o].sec=0;
Seg[o].maxnum=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1);
build(mid+1,r,o<<1|1);
pushup(o);
}
void update(int L,int R,int l,int r,int o,int c){//a[i]=min(a[i],c)
pushdown(o);
if(L<=l&&r<=R){
if(c>=Seg[o].maxx){
return;
}
else if(c<Seg[o].maxx&&c>Seg[o].sec){
Seg[o].sum-=(1LL*Seg[o].maxx-c)*Seg[o].maxnum;
Seg[o].maxx=c;
Seg[o].tag=c;
return;
}
else{
int mid=(l+r)>>1;
update(L,R,l,mid,o<<1,c);
update(L,R,mid+1,r,o<<1|1,c);
pushup(o);
return;
}
}
int mid=(l+r)>>1;
if(R<=mid)
update(L,R,l,mid,o<<1,c);
else if(L>mid)
update(L,R,mid+1,r,o<<1|1,c);
else{
update(L,R,l,mid,o<<1,c);
update(L,R,mid+1,r,o<<1|1,c);
}
pushup(o);
}
long long query_max(int L,int R,int l,int r,int o){
pushdown(o);
if(L<=l&&r<=R){
return Seg[o].maxx;
}
int mid=(l+r)>>1;
long long ans=0;
if(L<=mid)
ans=max(ans,query_max(L,R,l,mid,o<<1));
if(R>mid)
ans=max(ans,query_max(L,R,mid+1,r,o<<1|1));
return ans;
}
long long query_sum(int L,int R,int l,int r,int o){
pushdown(o);
if(L<=l&&r<=R){
return Seg[o].sum;
}
int mid=(l+r)>>1;
long long ans=0;
if(L<=mid)
ans+=query_sum(L,R,l,mid,o<<1);
if(R>mid)
ans+=query_sum(L,R,mid+1,r,o<<1|1);
return ans;
}
void init(void){
memset(Seg,0,sizeof(Seg));
memset(a,0,sizeof(a));
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
for(int i=1;i<=m;i++){
int opt,x,y,t;
scanf("%d %d %d",&opt,&x,&y);
if(opt==0){
scanf("%d",&t);
update(x,y,1,n,1,t);
}
else if(opt==1){
printf("%lld\n",query_max(x,y,1,n,1));
}
else{
printf("%lld\n",query_sum(x,y,1,n,1));
}
}
// init();
}
return 0;
}