P1033 · OFFICIAL SOLUTION

P1033 蝶恋花官方题解

Gioush OJ · P1033 蝶恋花

蝶恋花

【题意简述】

维护序列 $a_i$ 与历史最大值 $b_i$ 。支持区间加、区间取最小值、查询区间和、查询区间最大值、查询区间历史最大值。

【Hint】

区间取最小值只会影响当前最大值。若一个线段树结点的最大值大于 $v$ 且严格次大值小于 $v$ ，就可以只修改最大值那一批元素。

【提示】

每个结点维护最大值、严格次大值、最大值个数、区间和与历史最大值。区间加和历史最大值需要用标记同时维护“最大值位置”和“非最大值位置”。

【解法】

这是区间最值操作线段树。每个结点维护：

$\operatorname{Max}$ ：当前最大值；
$\operatorname{SecMax}$ ：严格次大值；
$\operatorname{MaxCnt}$ ：最大值个数；
$\operatorname{Sum}$ ：区间和；
$\operatorname{HisMax}$ ：历史最大值。

对区间取最小值 $v$ 时：

若 $\operatorname{Max}\le v$ ，没有影响；
若 $\operatorname{SecMax}<v<\operatorname{Max}$ ，只把最大值部分压到 $v$ ，可以整段打标记；
否则继续递归。

区间加会同时改变最大值与非最大值；历史最大值要求标记记录当前值变化与历史变化，因此代码中将最大值位置和其他位置分开维护。

【标记复合】

Data 维护区间长度、区间和、最大值、严格次大值、最大值个数与区间历史最大值。标记将元素分为“当前最大值”和“其余元素”两组，分别维护最终增加量与过程中的最大前缀增加量。

规定 $A\circ B$ 表示先执行 $B$ 再执行 $A$ 。以最大值组为例：

\begin{aligned} \operatorname{MaxAdd}_{A\circ B}&=\operatorname{MaxAdd}_B+\operatorname{MaxAdd}_A,\\ \operatorname{MaxHis}_{A\circ B}&=\max\left(\operatorname{MaxHis}_B,\operatorname{MaxAdd}_B+\operatorname{MaxHis}_A\right). \end{aligned}

区间加对应两组同时增加；当 $\operatorname{SecMax}<v<\operatorname{Max}$ 时，区间取最小值只使最大值组下降。不能整段执行时递归，沿用 Segment Tree Beats 的势能分析。

【复杂度】

均摊复杂度为 $\mathcal{O}((n+q)\log^2 n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/234Name:flutter.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 50001011#define LSon Node[Now].LeftSon12#define RSon Node[Now].RightSon13using namespace std;14const int INF=2000000000;15 16int n,m,In1,In2,In3,cnt=0,Line[MAXN];17 18struct Data{19    int Len,Max,SecMax,HisMax,MaxCnt;20    long long Sum;21};22 23struct tag{24    int MaxAdd,OtherAdd,MaxHis,OtherHis;25};26 27tag Empty(){return {0,0,0,0};}28Data Null(){return {0,-INF,-INF,-INF,0,0};}29 30Data operator+(const Data &A,const Data &B){31    if(!A.Len) return B;32    if(!B.Len) return A;33    Data Ret={A.Len+B.Len,0,0,max(A.HisMax,B.HisMax),0,A.Sum+B.Sum};34    if(A.Max==B.Max) Ret.Max=A.Max,Ret.MaxCnt=A.MaxCnt+B.MaxCnt,Ret.SecMax=max(A.SecMax,B.SecMax);35    else if(A.Max>B.Max) Ret.Max=A.Max,Ret.MaxCnt=A.MaxCnt,Ret.SecMax=max(A.SecMax,B.Max);36    else Ret.Max=B.Max,Ret.MaxCnt=B.MaxCnt,Ret.SecMax=max(A.Max,B.SecMax);37    return Ret;38}39 40Data operator*(const tag &Tag,const Data &B){41    Data Ret=B;42    Ret.HisMax=max(Ret.HisMax,Ret.Max+Tag.MaxHis);43    Ret.Sum+=1ll*Tag.MaxAdd*Ret.MaxCnt+1ll*Tag.OtherAdd*(Ret.Len-Ret.MaxCnt);44    Ret.Max+=Tag.MaxAdd;45    if(Ret.SecMax!=-INF) Ret.SecMax+=Tag.OtherAdd;46    return Ret;47}48 49tag operator*(const tag &A,const tag &B){50    tag Ret=B;51    Ret.MaxHis=max(Ret.MaxHis,Ret.MaxAdd+A.MaxHis);52    Ret.OtherHis=max(Ret.OtherHis,Ret.OtherAdd+A.OtherHis);53    Ret.MaxAdd+=A.MaxAdd;Ret.OtherAdd+=A.OtherAdd;54    return Ret;55}56 57struct node{58    int l,r,LeftSon,RightSon;59    Data Val;60    tag Tag;61}Node[MAXN<<2];62 63void Update(int Now){Node[Now].Val=Node[LSon].Val+Node[RSon].Val;}64 65void Mark(int Now,tag Tag){66    Node[Now].Val=Tag*Node[Now].Val;67    Node[Now].Tag=Tag*Node[Now].Tag;68    return;69}70 71void PushDown(int Now){72    tag Tag=Node[Now].Tag;73    if(!Tag.MaxAdd&&!Tag.OtherAdd&&!Tag.MaxHis&&!Tag.OtherHis) return;74    int Max=max(Node[LSon].Val.Max,Node[RSon].Val.Max);75    tag Other={Tag.OtherAdd,Tag.OtherAdd,Tag.OtherHis,Tag.OtherHis};76    if(Node[LSon].Val.Max==Max) Mark(LSon,Tag);else Mark(LSon,Other);77    if(Node[RSon].Val.Max==Max) Mark(RSon,Tag);else Mark(RSon,Other);78    Node[Now].Tag=Empty();79    return;80}81 82int Build(int l,int r){83    int Now=++cnt;84    Node[Now]={l,r,0,0,{r-l+1,-INF,-INF,-INF,0,0},Empty()};85    if(l==r){Node[Now].Val={1,Line[l],-INF,Line[l],1,Line[l]};return Now;}86    int Mid=(l+r)>>1;87    LSon=Build(l,Mid);88    RSon=Build(Mid+1,r);89    Update(Now);90    return Now;91}92 93void Modify(int Now,int l,int r,tag Tag){94    if(Node[Now].l>=l&&Node[Now].r<=r){Mark(Now,Tag);return;}95    else if(Node[Now].l>r||Node[Now].r<l) return;96    PushDown(Now);97    Modify(LSon,l,r,Tag);Modify(RSon,l,r,Tag);98    Update(Now);99    return;100}101 102void Limit(int Now,int l,int r,int Val){103    if(Node[Now].l>r||Node[Now].r<l||Node[Now].Val.Max<=Val) return;104    if(Node[Now].l>=l&&Node[Now].r<=r&&Node[Now].Val.SecMax<Val){105        Mark(Now,{Val-Node[Now].Val.Max,0,0,0});106        return;107    }108    PushDown(Now);109    Limit(LSon,l,r,Val);Limit(RSon,l,r,Val);110    Update(Now);111    return;112}113 114Data Query(int Now,int l,int r){115    if(Node[Now].l>=l&&Node[Now].r<=r) return Node[Now].Val;116    else if(Node[Now].l>r||Node[Now].r<l) return Null();117    PushDown(Now);118    return Query(LSon,l,r)+Query(RSon,l,r);119}120 121int main(){122    freopen("flutter.in","r",stdin);123    freopen("flutter.out","w",stdout);124    int c,T;125    scanf("%d%d",&c,&T);126    while(T-->0){127        scanf("%d%d",&n,&m);128        cnt=0;129        for(int i=1;i<=n;i++) scanf("%d",&Line[i]);130        Build(1,n);131        while(m-->0){132            scanf("%d%d%d",&In1,&In2,&In3);133            if(In1==1){scanf("%d",&In1);Modify(1,In2,In3,{In1,In1,In1,In1});}134            else if(In1==2){scanf("%d",&In1);Limit(1,In2,In3,In1);}135            else if(In1==3) printf("%lld\n",Query(1,In2,In3).Sum);136            else if(In1==4) printf("%d\n",Query(1,In2,In3).Max);137            else printf("%d\n",Query(1,In2,In3).HisMax);138        }139    }140    return 0;141}