Broadly speaking, a range chmin/chmax operation replaces every number in the range \([l,r]\) by its \(\max\) or \(\min\) with \(x\), that is, \(a_i=\max(a_i,x)\) or \(a_i=\min(a_i,x)\).
Maintain a sequence \(a\) under the following operations:
0 l r t: \(\forall l\le i\le r,~ a_i=\min(a_i,t)\).
1 l r: output \(\max\limits_{i=l}^r a_i\).
2 l r: output \(\sum\limits_{i=l}^r a_i\).
There are multiple test cases. It is guaranteed that \(T\le 100,~\sum n,\sum m\le 10^6\).
A range \(\min\) changes only the numbers greater than \(t\). So the operation no longer acts on the whole range, but on "the numbers in this range that are greater than \(t\)". This suggests the following approach: each node stores the maximum \(Max\) of its range, the second maximum \(Se\), the range sum \(Sum\), and the number \(Cnt\) of occurrences of the maximum. Now consider taking the \(\min\) of a range with \(t\).
If \(Max\le t\), this \(t\) has no effect, and we return immediately.
If \(Se<t < Max\), then \(t\) updates the maximum of the current range. We add \(Cnt(t-Max)\) to the range sum, set \(Max\) to \(t\), and apply a tag.
If \(t\le Se\), we cannot tell how many numbers the update affects. So we simply recurse into the children by brute force, and then pull up.
How fast is this algorithm? The potential method shows that it runs in \(O(m\log n)\). See the paper for the analysis.
#include<algorithm>#include<cctype>#include<iostream>usingnamespacestd;constexprintN=1e6+6;intt,n,m;inta[N];intmx[N<<2],se[N<<2],cn[N<<2],tag[N<<2];longlongsum[N<<2];voidpushup(intu){// pull up the informationconstintls=u<<1,rs=u<<1|1;sum[u]=sum[ls]+sum[rs];if(mx[ls]==mx[rs]){mx[u]=mx[rs];se[u]=max(se[ls],se[rs]);cn[u]=cn[ls]+cn[rs];}elseif(mx[ls]>mx[rs]){mx[u]=mx[ls];se[u]=max(se[ls],mx[rs]);cn[u]=cn[ls];}else{mx[u]=mx[rs];se[u]=max(mx[ls],se[rs]);cn[u]=cn[rs];}}voidpushtag(intu,inttg){// just apply the tag, no brute-force searchif(mx[u]<=tg)return;sum[u]+=(1ll*tg-mx[u])*cn[u];mx[u]=tag[u]=tg;}voidpushdown(intu){// push down the tagif(tag[u]==-1)return;pushtag(u<<1,tag[u]),pushtag(u<<1|1,tag[u]);tag[u]=-1;}voidbuild(intu=1,intl=1,intr=n){// build the treetag[u]=-1;if(l==r){sum[u]=mx[u]=a[l],se[u]=-1,cn[u]=1;return;}intmid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}voidmodify_min(intL,intR,intv,intu=1,intl=1,intr=n){if(mx[u]<=v)return;if(L<=l&&r<=R&&se[u]<v)returnpushtag(u,v);intmid=(l+r)>>1;pushdown(u);if(L<=mid)modify_min(L,R,v,u<<1,l,mid);if(mid<R)modify_min(L,R,v,u<<1|1,mid+1,r);pushup(u);}intquery_max(intL,intR,intu=1,intl=1,intr=n){// query the maximumif(L<=l&&r<=R)returnmx[u];intmid=(l+r)>>1,r1=-1,r2=-1;pushdown(u);if(L<=mid)r1=query_max(L,R,u<<1,l,mid);if(mid<R)r2=query_max(L,R,u<<1|1,mid+1,r);returnmax(r1,r2);}longlongquery_sum(intL,intR,intu=1,intl=1,intr=n){// sum of the valuesif(L<=l&&r<=R)returnsum[u];intmid=(l+r)>>1;longlongres=0;pushdown(u);if(L<=mid)res+=query_sum(L,R,u<<1,l,mid);if(mid<R)res+=query_sum(L,R,u<<1|1,mid+1,r);returnres;}voidgo(){// as the problem statement requirescin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];build();for(inti=1;i<=m;i++){intop,x,y,z;cin>>op>>x>>y;if(op==0)cin>>z,modify_min(x,y,z);elseif(op==1)cout<<query_max(x,y)<<'\n';elsecout<<query_sum(x,y)<<'\n';}}signedmain(){cin.tie(nullptr)->sync_with_stdio(false);cin>>t;while(t--)go();return0;}
Maintain a sequence \(a\) under the following operations:
1 l r x: \(\forall l\le i\le r,~ a_i=a_i+x\).
2 l r x: \(\forall l\le i\le r,~ a_i=\max(a_i,x)\).
3 l r x: \(\forall l\le i\le r,~ a_i=\min(a_i,x)\).
4 l r: output \(\sum\limits_{i=l}^r a_i\).
5 l r: output \(\max\limits_{i=l}^r a_i\).
6 l r: output \(\min\limits_{i=l}^r a_i\).
\(n,m\le 5\times 10^5,~|a_i|\le 10^8\). Every operation of type \(1\) has \(|x|\le 10^3\), and all other operations have \(|x|\le10^8\).
In the same way, we maintain the maximum, the second maximum, the count of the maximum, the minimum, the second minimum, the count of the minimum, and the range sum. On top of this information we need tags for range \(\max\), range \(\min\) and range addition. Unlike the previous problem, this raises the question of the order in which tags are pushed down. We use the following strategy:
The range addition tag has the highest priority; the other two kinds of tags are on an equal footing.
When a tag \(v\) is added to a node, we update the satellite data and the node's range addition tag with \(v\), and we also update its range \(\max\) and range \(\min\) tags with this \(v\).
When a node takes the \(\min\) with \(v\) (we ignore the brute-force search here and assume the tag can be applied), we update the satellite data and also compare \(v\) with the range \(\max\) tag. If \(v\) is smaller than the range \(\max\) tag, every number ends up equal to \(v\), so we set the range \(\max\) tag to \(v\) as well. Otherwise we leave it alone.
Taking the \(\max\) of a range with \(v\) works the same way.
When maintaining this information, the sets of numbers may coincide if there are only one or two numbers: a number can be both the maximum and the second minimum, for example. Such cases need special-casing.
#include<iostream>usingnamespacestd;constexprintN=5e5+5,SZ=N<<2,INF=0x7fffffff;intn,m;inta[N];structdata{intmx,mx2,mn,mn2,cmx,cmn,tmx,tmn,tad;longlongsum;}t[SZ];voidpushup(intu){constintlu=u<<1,ru=u<<1|1;t[u].sum=t[lu].sum+t[ru].sum;if(t[lu].mx==t[ru].mx){t[u].mx=t[lu].mx,t[u].cmx=t[lu].cmx+t[ru].cmx;t[u].mx2=max(t[lu].mx2,t[ru].mx2);}elseif(t[lu].mx>t[ru].mx){t[u].mx=t[lu].mx,t[u].cmx=t[lu].cmx;t[u].mx2=max(t[lu].mx2,t[ru].mx);}else{t[u].mx=t[ru].mx,t[u].cmx=t[ru].cmx;t[u].mx2=max(t[lu].mx,t[ru].mx2);}if(t[lu].mn==t[ru].mn){t[u].mn=t[lu].mn,t[u].cmn=t[lu].cmn+t[ru].cmn;t[u].mn2=min(t[lu].mn2,t[ru].mn2);}elseif(t[lu].mn<t[ru].mn){t[u].mn=t[lu].mn,t[u].cmn=t[lu].cmn;t[u].mn2=min(t[lu].mn2,t[ru].mn);}else{t[u].mn=t[ru].mn,t[u].cmn=t[ru].cmn;t[u].mn2=min(t[lu].mn,t[ru].mn2);}}voidpush_add(intu,intl,intr,intv){// while updating the addition tag, also update the $\min$ and $\max$ tagst[u].sum+=(r-l+1ll)*v;t[u].mx+=v,t[u].mn+=v;if(t[u].mx2!=-INF)t[u].mx2+=v;if(t[u].mn2!=INF)t[u].mn2+=v;if(t[u].tmx!=-INF)t[u].tmx+=v;if(t[u].tmn!=INF)t[u].tmn+=v;t[u].tad+=v;}voidpush_min(intu,inttg){// remember to compare with the $\max$ tagif(t[u].mx<=tg)return;t[u].sum+=(tg*1ll-t[u].mx)*t[u].cmx;if(t[u].mn2==t[u].mx)t[u].mn2=tg;// !!!if(t[u].mn==t[u].mx)t[u].mn=tg;// !!!!!if(t[u].tmx>tg)t[u].tmx=tg;// update the $\max$ tagt[u].mx=tg,t[u].tmn=tg;}voidpush_max(intu,inttg){if(t[u].mn>tg)return;t[u].sum+=(tg*1ll-t[u].mn)*t[u].cmn;if(t[u].mx2==t[u].mn)t[u].mx2=tg;if(t[u].mx==t[u].mn)t[u].mx=tg;if(t[u].tmn<tg)t[u].tmn=tg;t[u].mn=tg,t[u].tmx=tg;}voidpushdown(intu,intl,intr){constintlu=u<<1,ru=u<<1|1,mid=(l+r)>>1;if(t[u].tad)push_add(lu,l,mid,t[u].tad),push_add(ru,mid+1,r,t[u].tad);if(t[u].tmx!=-INF)push_max(lu,t[u].tmx),push_max(ru,t[u].tmx);if(t[u].tmn!=INF)push_min(lu,t[u].tmn),push_min(ru,t[u].tmn);t[u].tad=0,t[u].tmx=-INF,t[u].tmn=INF;}voidbuild(intu=1,intl=1,intr=n){t[u].tmn=INF,t[u].tmx=-INF;// set to the extreme valuesif(l==r){t[u].sum=t[u].mx=t[u].mn=a[l];t[u].mx2=-INF,t[u].mn2=INF;t[u].cmx=t[u].cmn=1;return;}intmid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}voidadd(intL,intR,intv,intu=1,intl=1,intr=n){if(R<l||r<L)return;if(L<=l&&r<=R)returnpush_add(u,l,r,v);// !!! forgot the returnintmid=(l+r)>>1;pushdown(u,l,r);add(L,R,v,u<<1,l,mid),add(L,R,v,u<<1|1,mid+1,r);pushup(u);}voidtomin(intL,intR,intv,intu=1,intl=1,intr=n){if(R<l||r<L||t[u].mx<=v)return;if(L<=l&&r<=R&&t[u].mx2<v)returnpush_min(u,v);// BUG: forgot to returnintmid=(l+r)>>1;pushdown(u,l,r);tomin(L,R,v,u<<1,l,mid),tomin(L,R,v,u<<1|1,mid+1,r);pushup(u);}voidtomax(intL,intR,intv,intu=1,intl=1,intr=n){if(R<l||r<L||t[u].mn>=v)return;if(L<=l&&r<=R&&t[u].mn2>v)returnpush_max(u,v);intmid=(l+r)>>1;pushdown(u,l,r);tomax(L,R,v,u<<1,l,mid),tomax(L,R,v,u<<1|1,mid+1,r);pushup(u);}longlongqsum(intL,intR,intu=1,intl=1,intr=n){if(R<l||r<L)return0;if(L<=l&&r<=R)returnt[u].sum;intmid=(l+r)>>1;pushdown(u,l,r);returnqsum(L,R,u<<1,l,mid)+qsum(L,R,u<<1|1,mid+1,r);}longlongqmax(intL,intR,intu=1,intl=1,intr=n){if(R<l||r<L)return-INF;if(L<=l&&r<=R)returnt[u].mx;intmid=(l+r)>>1;pushdown(u,l,r);returnmax(qmax(L,R,u<<1,l,mid),qmax(L,R,u<<1|1,mid+1,r));}longlongqmin(intL,intR,intu=1,intl=1,intr=n){if(R<l||r<L)returnINF;if(L<=l&&r<=R)returnt[u].mn;intmid=(l+r)>>1;pushdown(u,l,r);returnmin(qmin(L,R,u<<1,l,mid),qmin(L,R,u<<1|1,mid+1,r));}intmain(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(inti=1;i<=n;i++)cin>>a[i];build();cin>>m;for(inti=1;i<=m;i++){intop,l,r,x;cin>>op>>l>>r;if(op<=3)cin>>x;if(op==1)add(l,r,x);elseif(op==2)tomax(l,r,x);elseif(op==3)tomin(l,r,x);elseif(op==4)cout<<qsum(l,r)<<'\n';elseif(op==5)cout<<qmax(l,r)<<'\n';elsecout<<qmin(l,r)<<'\n';}return0;}
Ruyi Ji proved that this algorithm runs in \(O(m\log^2 n)\).
Mzl loves segment tree
There are two sequences \(A\) and \(B\); initially every number in \(B\) is \(0\). The operations to support are:
Range \(\min\) on \(A\)
Range \(\max\) on \(A\)
Range addition on \(A\)
Query a range sum of \(B\)
After each operation, if the value of \(A_i\) has changed, add \(1\) to \(B_i\). \(n,m\le 3\times 10^5\).
Start with the easiest operation, range addition. As long as \(x\neq 0\), every number in the range changes, so one range addition on B is enough.
For the range chmin/chmax operations, notice that applying tags and pushing them down correspond one-to-one to updates of the array \(B\). In essence you have split the numbers of the sequence into three classes, the maximum, the minimum and everything else, and you maintain each class separately (you never actually build the sets of extreme values, but that does not get in the way). So whenever you apply a tag, update the information of \(B\) along the way (note: this updates its information, it does not put a tag on \(B\)!). To answer a query, descend in \(A\) and update the information of \(B\) as you push tags down. Once you reach the nodes you need, return the information of \(B\). In effect, the information about the extreme values is handed to \(B\) to maintain. You still have to deal with overlapping sets of numbers.
Maintain two sequences \(a\) and \(b\) under the following operations:
1 l r x: \(\forall l\le i\le r,~ a_i=\min(a_i,x)\).
2 l r x: \(\forall l\le i\le r,~ b_i=\min(b_i,x)\).
3 l r x: \(\forall l\le i\le r,~ a_i=a_i+x\).
4 l r x: \(\forall l\le i\le r,~ b_i=b_i+x\).
5 l r: output \(\max\limits_{i=l}^r (a_i+b_i)\).
\(n,m\le 3\times 10^5,~|a_i|,|b_i|,|x|\le 10^9\).
We split the candidate answers \(A_i+B_i\) in a range \([l,r]\) into four classes: neither \(A_i\) nor \(B_i\) is the range maximum of its sequence \(A\) or \(B\); \(A_i\) is the range maximum of \(A\) but \(B_i\) is not the range maximum of \(B\); \(A_i\) is not the range maximum of \(A\) but \(B_i\) is the range maximum of \(B\); and both \(A_i\) and \(B_i\) are the range maxima of \(A\) and \(B\). Denote them by \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) respectively. We also maintain the range maximum and second maximum of \(A\) and \(B\) as usual. When range addition tags and \(\min\) tags are pushed down, the maxima and second maxima of \(A\) and \(B\) are handled as in the two examples above. A \(\min\) tag on \(A\) affects \(C_{1,1}\) and \(C_{1,0}\), and a tag on \(B\) affects \(C_{1,1}\) and \(C_{0,1}\). An addition on \(A\) or \(B\) affects all of \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\). Just watch for the boundary cases where \(C_{0,0},C_{1,0},C_{0,1}\) do not exist (for example, for a range \([i,i]\) only the maxima of \(A\) and \(B\) and \(C_{1,1}\) exist).
Next, how do we maintain \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) in pushup? Once the maxima of \(A\) and \(B\) have been updated, we distinguish cases by whether the maxima of \(A\) and \(B\) at the left and right children equal those at the current node. We describe the left child; the right child is handled in the same way:
If the left child's maxima of \(A\) and \(B\) both equal those of the current node, the left child's \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) contribute to the current node's \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) respectively.
If the left child's maximum of \(A\) equals the current node's maximum of \(A\) but the maxima of \(B\) differ, the left child's \(C_{1,0},C_{1,1}\) contribute to this node's \(C_{1,0}\), and its \(C_{0,0},C_{0,1}\) contribute to this node's \(C_{0,0}\).
If the left child's maximum of \(A\) differs from the current node's maximum of \(A\) but the maxima of \(B\) are equal, the left child's \(C_{0,1},C_{1,1}\) contribute to this node's \(C_{0,1}\), and its \(C_{0,0},C_{1,0}\) contribute to this node's \(C_{0,0}\).
If neither of the left child's maxima of \(A\) and \(B\) equals that of the current node, the left child's \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) contribute only to this node's \(C_{0,0}\).
The answer is \(\max(C_{0,0},C_{1,0},C_{0,1},C_{1,1})\) taken over the result of the range query.
Since range \(\min\) and range addition are maintained together, the complexity is still \(O(m\log^2 n)\).
#include<algorithm>#include<cstdint>#include<iostream>usingi64=int64_t;constexprintN=300010;constexpri64INF=1145141919810114514ll;intn,q,op,l,r;inta[N],b[N];intlc(intu){return(u<<1);}intrc(intu){return(u<<1)|1;}structnode{i64mx_ab[2][2];// 0: not max A or B; 1: is max A or Bi64max_val(){returnstd::max({mx_ab[0][0],mx_ab[0][1],mx_ab[1][0],mx_ab[1][1]});}i64mx1[2],mx2[2];// 0: A; 1: Bi64tag_add[2],tag_mn[2];voidclr_tag(){tag_add[0]=tag_add[1]=0,tag_mn[0]=tag_mn[1]=INF;}voidinit(i64a,i64b){mx1[0]=a,mx1[1]=b,mx2[0]=mx2[1]=-INF;mx_ab[1][1]=a+b,mx_ab[0][1]=mx_ab[1][0]=mx_ab[0][0]=-INF;}voidmodify_mn(i64tg,boolid)// id 0: A; 1: B{if(mx1[id]<=tg)return;mx_ab[1][1]+=(mx_ab[1][1]>-INF)?(tg-mx1[id]):0;mx_ab[!id][id]+=(mx_ab[!id][id]>-INF)?(tg-mx1[id]):0;mx1[id]=tag_mn[id]=tg;}voidmodify_add(i64tg,boolid)// id 0: A; 1: B{for(inti=0;i<2;++i)for(intj=0;j<2;++j)mx_ab[i][j]+=(mx_ab[i][j]>-INF)?tg:0;mx1[id]+=tg,mx2[id]+=(mx2[id]>-INF)?tg:0;tag_mn[id]+=(tag_mn[id]<INF)?tg:0,tag_add[id]+=tg;}voidpushup(constnode&l,constnode&r){for(inti=0;i<2;++i){if(l.mx1[i]==r.mx1[i])mx1[i]=l.mx1[i],mx2[i]=std::max(l.mx2[i],r.mx2[i]);elseif(l.mx1[i]>r.mx1[i])mx1[i]=l.mx1[i],mx2[i]=std::max(l.mx2[i],r.mx1[i]);elsemx1[i]=r.mx1[i],mx2[i]=std::max(l.mx1[i],r.mx2[i]);}if(l.mx1[0]==mx1[0]&&l.mx1[1]==mx1[1]){mx_ab[1][1]=l.mx_ab[1][1],mx_ab[0][1]=l.mx_ab[0][1];mx_ab[1][0]=l.mx_ab[1][0],mx_ab[0][0]=l.mx_ab[0][0];}elseif(l.mx1[0]==mx1[0]&&l.mx1[1]!=mx1[1]){mx_ab[1][1]=mx_ab[0][1]=-INF;mx_ab[1][0]=std::max(l.mx_ab[1][1],l.mx_ab[1][0]);mx_ab[0][0]=std::max(l.mx_ab[0][1],l.mx_ab[0][0]);}elseif(l.mx1[0]!=mx1[0]&&l.mx1[1]==mx1[1]){mx_ab[1][1]=mx_ab[1][0]=-INF;mx_ab[0][1]=std::max(l.mx_ab[1][1],l.mx_ab[0][1]);mx_ab[0][0]=std::max(l.mx_ab[1][0],l.mx_ab[0][0]);}else{mx_ab[1][1]=mx_ab[0][1]=mx_ab[1][0]=-INF;mx_ab[0][0]=std::max({l.mx_ab[0][0],l.mx_ab[0][1],l.mx_ab[1][0],l.mx_ab[1][1]});}if(r.mx1[0]==mx1[0]&&r.mx1[1]==mx1[1]){mx_ab[1][1]=std::max(mx_ab[1][1],r.mx_ab[1][1]);mx_ab[0][1]=std::max(mx_ab[0][1],r.mx_ab[0][1]);mx_ab[1][0]=std::max(mx_ab[1][0],r.mx_ab[1][0]);mx_ab[0][0]=std::max(mx_ab[0][0],r.mx_ab[0][0]);}elseif(r.mx1[0]==mx1[0]&&r.mx1[1]!=mx1[1]){mx_ab[1][0]=std::max({mx_ab[1][0],r.mx_ab[1][1],r.mx_ab[1][0]});mx_ab[0][0]=std::max({mx_ab[0][0],r.mx_ab[0][1],r.mx_ab[0][0]});}elseif(r.mx1[0]!=mx1[0]&&r.mx1[1]==mx1[1]){mx_ab[0][1]=std::max({mx_ab[0][1],r.mx_ab[1][1],r.mx_ab[0][1]});mx_ab[0][0]=std::max({mx_ab[0][0],r.mx_ab[1][0],r.mx_ab[0][0]});}elsemx_ab[0][0]=std::max({mx_ab[0][0],r.mx_ab[0][0],r.mx_ab[0][1],r.mx_ab[1][0],r.mx_ab[1][1]});}}tr[N<<2];voidpushup(intu){tr[u].pushup(tr[lc(u)],tr[rc(u)]);}voidpushdown(intu){for(inti=0;i<2;++i)if(tr[u].tag_add[i])tr[lc(u)].modify_add(tr[u].tag_add[i],i),tr[rc(u)].modify_add(tr[u].tag_add[i],i);for(inti=0;i<2;++i)if(tr[u].tag_mn[i]<INF)tr[lc(u)].modify_mn(tr[u].tag_mn[i],i),tr[rc(u)].modify_mn(tr[u].tag_mn[i],i);tr[u].clr_tag();}void_build(intu,intL,intR){tr[u].clr_tag();if(L==R)returntr[u].init(a[L],b[L]);intM=(L+R)>>1;_build(lc(u),L,M),_build(rc(u),M+1,R),pushup(u);}voidbuild(){_build(1,1,n);}void_modify_mn(intu,intl,intr,intL,intR,intv,booli){if(L>r||R<l||tr[u].mx1[i]<=v)return;if(l<=L&&R<=r&&tr[u].mx2[i]<v)returntr[u].modify_mn(v,i);pushdown(u);intM=(L+R)>>1;_modify_mn(lc(u),l,r,L,M,v,i),_modify_mn(rc(u),l,r,M+1,R,v,i);pushup(u);}voidmodify_mn(intl,intr,intv,booli){_modify_mn(1,l,r,1,n,v,i);}void_modify_add(intu,intl,intr,intL,intR,intv,booli){if(L>r||R<l)return;if(l<=L&&R<=r)returntr[u].modify_add(v,i);pushdown(u);intM=(L+R)>>1;_modify_add(lc(u),l,r,L,M,v,i),_modify_add(rc(u),l,r,M+1,R,v,i);pushup(u);}voidmodify_add(intl,intr,intv,booli){_modify_add(1,l,r,1,n,v,i);}node_query(intu,intl,intr,intL,intR){if(l<=L&&R<=r)returntr[u];pushdown(u);intM=(L+R)>>1;if(r<=M)return_query(lc(u),l,r,L,M);if(l>M)return_query(rc(u),l,r,M+1,R);noderet;node_l=_query(lc(u),l,M,L,M),_r=_query(rc(u),M+1,r,M+1,R);ret.pushup(_l,_r);returnret;}nodequery(intl,intr){return_query(1,l,r,1,n);}usingstd::cin;usingstd::cout;intmain(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>q;for(inti=1;i<=n;++i)cin>>a[i];for(inti=1;i<=n;++i)cin>>b[i];build();while(q--){cin>>op>>l>>r;intx;switch(op){case1:cin>>x;modify_mn(l,r,x,0);break;case2:cin>>x;modify_mn(l,r,x,1);break;case3:cin>>x;modify_add(l,r,x,0);break;case4:cin>>x;modify_add(l,r,x,1);break;case5:cout<<query(l,r).max_val()<<'\n';break;default:break;}}}
Summary
This section gave four examples. They showed, in turn, how to maintain the basic range chmin/chmax operations, how to prioritize several tags, the idea of splitting the numbers into classes, and how to maintain several classifications at once. At its core, handling range chmin/chmax means maintaining information about the numbers class by class and merging it efficiently. The next section looks at historical range maximum/minimum problems.
Historical maximum/minimum problems
Historical maximum/minimum is not persistence
Note that the historical maximum/minimum problems of this section are not the same thing as so-called persistent data structures. We call this special class of problems historical maximum/minimum problems. They fall into three kinds.
Historical maximum
Put simply, the historical maximum of a position is the largest number that has ever appeared at that position. Formally, we define an auxiliary array \(B\) that is initially identical to \(A\). After every operation on \(A\), we take the \(\max\) over the whole array:
\[
\forall i\in[1,n],\ B_i=\max(B_i,A_i)
\]
We then call \(B_i\) the historical maximum of this position.
Historical minimum
The definition is analogous to that of the historical maximum: after every operation on \(A\), we take the \(\min\) over the whole array. We then call \(B_i\) the historical minimum of this position.
Historical sum
The auxiliary array \(B\) is initially all \(0\). After every operation, we add the whole array \(A\) to the array \(B\):
\[
\forall i\in[1,n], \ B_i=B_i+A_i
\]
We call \(B_i\) the historical sum at position \(i\).
Below we discuss historical maximum/minimum problems in four classes.
The sequences \(A\) and \(B\) are initially identical:
Range assignment of \(x\) on \(A\)
Range addition of \(x\) on \(A\)
Query a range \(\max\) of \(A\)
Query a range \(\max\) of \(B\)
After each operation we perform the update \(\forall i\in [1,n],\ B_i=\max(B_i,A_i)\). \(n,m\le 10^5\).
Ignore operation 1 for now. The only update is then range addition, and we maintain a tag \(Add\), the amount added to the current range; this tag takes care of the range \(\max\). Now consider the historical range \(\max\). We define a tag \(Pre\) with the following meaning: the historical maximum of the \(Add\) tag during the lifetime of this tag.
This definition may be rather vague, so let us first explain the lifetime of a tag. A tag goes through the following stages:
It is created at node \(u\).
Node \(u\) receives a number of new tags, and the tag is merged with them (with tags of the same kind, that is).
The tag of node \(u\) is pushed down to the children of \(u\), and the tag of \(u\) is cleared.
The lifetime of the tag of node \(u\) runs from step 1 until just before step 3. When two tags are merged they become a single tag, so their lifetimes merge as well (the lifetime starts at the earlier of the two creation times). Equivalently, the lifetime is the period from the last time this node's tag was pushed down until now.
Why define a lifetime? With this notion we can prove that during the lifetime of a node's tag none of its children change in any way: they stay in the state they were in before the lifetime began. The reason is simple: you push no tag down during that period.
This guarantees that the historical maximum of \(Add\) during the current tag's lifetime can be applied to the tags and information of the children, because neither changed during that time. So when we push the tag of \(u\) down to its child \(s\), we get
The information is updated in the same way, using the corresponding tags.
Now consider operation 1.
A range assignment makes all the numbers equal. After that, whether the range is added to, subtracted from or assigned, all its numbers remain equal (unless you end the current tag's lifetime by pushing the tag down). So we can treat every tag after the first range assignment as a range assignment tag. In other words, the lifetime of a tag splits roughly into two phases:
A merge of several addition/subtraction tags; no assignment tag has been received yet.
An assignment tag; there are no addition/subtraction tags as such (they are converted into assignment tags).
So we split the node's Pre tag into \((P_1,P_2)\): \(P_1\) is the maximum addition/subtraction tag of the first phase, and \(P_2\) is the maximum assignment tag of the second phase. Tags are pushed down and information is updated in a similar way. This takes \(O(m\log n)\) time (mind you, this problem has no range chmin/chmax with \(x\)!).
#include<algorithm>#include<climits>#include<iostream>usingnamespacestd;usingll=longlong;constexprintN=1e5+7;structTree{intmx,_mx;// range maximum, historical range maximumintad,_ad;// range addition tag, historical maximum addition tag of the phaseintst,_st;// range assignment value, historical maximum assignment tag of the phase}g[N*4];inta[N];intn,m;#define ls u * 2#define rs u * 2 + 1#define mid (l + r) / 2voidpushup(intu){g[u].mx=max(g[ls].mx,g[rs].mx);g[u]._mx=max(g[ls]._mx,g[rs]._mx);}voidpushadd(intu,intv,int_v){g[u]._mx=max(g[u]._mx,g[u].mx+_v),g[u].mx+=v;if(g[u].st==INT_MIN)g[u]._ad=max(g[u]._ad,g[u].ad+_v),g[u].ad+=v;elseg[u]._st=max(g[u]._st,g[u].st+_v),g[u].st+=v;}voidpushset(intu,intv,int_v){g[u]._mx=max(g[u]._mx,_v),g[u].mx=v;g[u]._st=max(g[u]._st,_v),g[u].st=v;}voidpushdown(intu,intl,intr){if(g[u].ad||g[u]._ad)pushadd(ls,g[u].ad,g[u]._ad),pushadd(rs,g[u].ad,g[u]._ad),g[u].ad=g[u]._ad=0;if(g[u].st!=INT_MIN||g[u]._st!=INT_MIN)pushset(ls,g[u].st,g[u]._st),pushset(rs,g[u].st,g[u]._st),g[u].st=g[u]._st=INT_MIN;}voidbuild(intu=1,intl=1,intr=n){g[u]._st=g[u].st=INT_MIN;if(l==r){g[u].mx=a[l];g[u]._mx=a[l];return;}build(ls,l,mid),build(rs,mid+1,r);pushup(u);}intL,R;voidadd(intv,intu=1,intl=1,intr=n){if(R<l||r<L)return;if(L<=l&&r<=R)returnpushadd(u,v,max(v,0));pushdown(u,l,r);add(v,ls,l,mid),add(v,rs,mid+1,r);pushup(u);}voidtset(intv,intu=1,intl=1,intr=n){if(R<l||r<L)return;if(L<=l&&r<=R)returnpushset(u,v,v);pushdown(u,l,r);tset(v,ls,l,mid),tset(v,rs,mid+1,r);pushup(u);}intqmax(intu=1,intl=1,intr=n){if(R<l||r<L)returnINT_MIN;if(L<=l&&r<=R)returng[u].mx;pushdown(u,l,r);returnmax(qmax(ls,l,mid),qmax(rs,mid+1,r));}intqmaxh(intu=1,intl=1,intr=n){if(R<l||r<L)returnINT_MIN;if(L<=l&&r<=R)returng[u]._mx;pushdown(u,l,r);returnmax(qmaxh(ls,l,mid),qmaxh(rs,mid+1,r));}intmain(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(inti=1;i<=n;++i)cin>>a[i];build();intm,z;cin>>m;for(inti=1;i<=m;++i){charop;cin>>op;while(op==' '||op=='\r'||op=='\n')cin>>op;cin>>L>>R;intx;if(op=='Q')cout<<qmax()<<'\n';elseif(op=='A')cout<<qmaxh()<<'\n';elseif(op=='P')cin>>x,add(x);elsecin>>x,tset(x);}return0;}