我第一次出的一道比较正经的菜题，欢迎大家来切哦。
感谢魔法少女老干妈 GM_Joanna_ 的支持
对于操作 1，3：
注意到 1e9 的数据至多 5 此操作就能把一个位置变为 0，这个次数可视为常数。
考虑每个位置暴力改，也只会递归 \(5\times n\log n\) 次。
对于 3 操作，考虑最坏的情况，每次把一些数还原成 1e9。
注意到 3 操作后一些数是相同的，那么对于相同的数，就可以直接进行区间 1 操作。
线段树上区间操作复杂度 \(O(\log n)\)。
总复杂度 \(O(n\log ^2 n)\)。
对于操作 2：
吉司机线段树维护即可。
简略提一下吉司机线段树。记当前区间最大值为 \(mx\)，次大值为 \(se\)。现在有如下三种情况：
- \(mx\leq v\)，直接返回。
- \(se<v \leq mx\)，只修改当前区间最大值，可以打标记维护。
- \(v \leq se\)，暴力递归修改，若在叶子节点，直接修改最大值。
证一下时间复杂度
- 递归次数与值域（不同数值个数）相关，因为相同的数第二种情况可以直接进行区间操作。
- 每次递归条件是 \(v \leq se < mx\)，则至少会令 \(se=mx=v\)，显然值域至少 \(-1\)。
- 不论区间修改还是单点修改，最多只会令值域 \(+1\)。
- 线段树 \(\log n\) 层，每层值域 \(n\)，区间修改+单点修改次数 \(n\log n\) 次，故总复杂度 \(O(n\log^2 n)\)。
一些细节：
- 由于要打区间覆盖和修改最大值的两种标记，要注意下传标记的顺序。
- \(\log\) 函数自己手写，用换底公式可能有精度误差。
- 暴力进行 \(\log\) 操作到叶子节点时，注意把标记给清空（这鬼地方我调半天）。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,m,a[N];
struct SegmentTree{
int mx[N<<2],se[N<<2],c[N<<2],tag[N<<2],tag_mx[N<<2];
ll sum[N<<2];
#define lc k<<1
#define rc k<<1|1
#define mid ((l+r)>>1)
inline int max(int x,int y) {return x>y?x:y;}
inline int log(int x,int k)
{
if(x==0) return 0;
ll res=0,t=1;
while(t<=x) res++,t*=k;
return res-1;
}
inline void pushup(int k)
{
sum[k]=sum[lc]+sum[rc];
if(mx[lc]==mx[rc])
{
mx[k]=mx[lc];
se[k]=max(se[lc],se[rc]);
c[k]=c[lc]+c[rc];
}
else if(mx[lc]>mx[rc])
{
mx[k]=mx[lc];
se[k]=max(se[lc],mx[rc]);
c[k]=c[lc];
}
else
{
mx[k]=mx[rc];
se[k]=max(mx[lc],se[rc]);
c[k]=c[rc];
}
}
inline void pushtag(int k,int l,int r,int v)
{
tag[k]=mx[k]=v;
c[k]=r-l+1;
sum[k]=1ll*(r-l+1)*v;
se[k]=-1;
}
inline void push_mx(int k,int l,int r,int v)
{
if(~tag[k])
{
if(tag[k]<=v) return;
tag[k]=mx[k]=v;
sum[k]=1ll*(r-l+1)*v;
}
else
{
if(mx[k]<=v) return;
sum[k]-=1ll*c[k]*(mx[k]-v);
mx[k]=tag_mx[k]=v;
}
}
inline void pushdown(int k,int l,int r)
{
if(~tag[k])
{
pushtag(lc,l,mid,tag[k]);
pushtag(rc,mid+1,r,tag[k]);
tag[k]=-1,tag_mx[k]=-1;
}
if(~tag_mx[k])
{
push_mx(lc,l,mid,tag_mx[k]);
push_mx(rc,mid+1,r,tag_mx[k]);
tag_mx[k]=-1;
}
}
void build(int k=1,int l=1,int r=n)
{
tag[k]=tag_mx[k]=-1;
if(l==r) return sum[k]=mx[k]=a[l],c[k]=1,se[k]=-1,void();
build(lc,l,mid),build(rc,mid+1,r);
pushup(k);
}
void upd_log(int x,int y,int v,int k=1,int l=1,int r=n)
{
if(mx[k]<=0) return;
if(l>=x&&r<=y&&~tag[k]) return pushtag(k,l,r,log(tag[k],v)),void();
if(l==r)
{
mx[k]=log(mx[k],v);
sum[k]=mx[k];
tag[k]=tag_mx[k]=-1;
return;
}
pushdown(k,l,r);
if(x<=mid) upd_log(x,y,v,lc,l,mid);
if(mid<y) upd_log(x,y,v,rc,mid+1,r);
pushup(k);
}
void upd_min(int x,int y,int v,int k=1,int l=1,int r=n)
{
if(mx[k]<=v) return;
if(l>=x&&r<=y&&se[k]<v) return push_mx(k,l,r,v);
pushdown(k,l,r);
if(x<=mid) upd_min(x,y,v,lc,l,mid);
if(mid<y) upd_min(x,y,v,rc,mid+1,r);
pushup(k);
}
void upd_cov(int x,int y,int v,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return pushtag(k,l,r,v);
pushdown(k,l,r);
if(x<=mid) upd_cov(x,y,v,lc,l,mid);
if(mid<y) upd_cov(x,y,v,rc,mid+1,r);
pushup(k);
}
ll query(int x,int y,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return sum[k];
pushdown(k,l,r);
ll res=0;
if(x<=mid) res=query(x,y,lc,l,mid);
if(mid<y) res+=query(x,y,rc,mid+1,r);
return res;
}
}T;
inline int rd()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++) a[i]=rd();
T.build();
while(m--)
{
int op=rd(),l=rd(),r=rd(),x;
if(op!=4) x=rd();
if(op==1) T.upd_log(l,r,x);
else if(op==2) T.upd_min(l,r,x);
else if(op==3) T.upd_cov(l,r,x);
else printf("%lld\n",T.query(l,r));
}
}