自动搬运

查看原文

来自洛谷，原作者为

	Yonder Morose Dreamer

搬运于2025-08-24 22:59:25，当前版本为作者最后更新于2024-06-12 14:02:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑势能线段树，要维护的有：区间最大值（$Max$），区间最小值（$Min$），区间内每个数字与第一个比它大的小 Y 喜欢的数字的差的最小值（$Mix$）。

对于一操作，判断 $Mix$ 是否小于等于 $x$，若是则用加标记，否则直接暴力修改，每个数字最多只会被暴力修改 5 次。

对于二操作，直接暴力乘即可，每个数顶多会被乘 19 次。

对于三操作就是普通的区间覆盖，但是它很明显会影响一、二操作的时间复杂度，但只要我们在进行一、二操作的暴力修改前判断一下 $Max$ 是不是等于 $Min$ 即可。

四操作就判断 $Mix$ 是否为零即可，若是就输出 $Mix$ 为零的数的个数。

Code

#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
static char buf[4500000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,4500000,stdin),p1==p2)?EOF:*p1++
#endif
using namespace std;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return x;
}inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
const int N=5e5+5;
int n,m,a[N],x=42,f[N],nex[N],op,l,r,c;
int add[N<<2],Max[N<<2],Min[N<<2],Mix[N<<2],cnt[N<<2],tag[N<<2],Q[N<<2];
inline void push_up(int p){
    register int ls=p<<1,rs=p<<1|1;
	Max[p]=Max[Max[ls]>Max[rs]?ls:rs];
	Min[p]=Min[Min[ls]<Min[rs]?ls:rs];
	Mix[p]=Mix[Mix[ls]<Mix[rs]?ls:rs];
	if(Mix[ls]==Mix[rs]) cnt[p]=cnt[ls]+cnt[rs];
	else cnt[p]=cnt[Mix[ls]<Mix[rs]?ls:rs];
}
inline void fc(int p,int c){add[p]=0,tag[p]=c,cnt[p]=Q[p],Mix[p]=nex[c]-c,Max[p]=Min[p]=c;}
inline void fa(int p,int c){add[p]+=c;Min[p]+=c;Max[p]+=c;Mix[p]-=c;}
inline void push_down(int p){
	if(tag[p]){
	    if(add[p]) tag[p]+=add[p],add[p]=0;
	    fc(p<<1,tag[p]),fc(p<<1|1,tag[p]),tag[p]=0;
	    return;
	}
	if(add[p]) fa(p<<1,add[p]),fa(p<<1|1,add[p]),add[p]=0;
}
inline void Build(int p=1,int pl=1,int pr=n){
	Q[p]=pr-pl+1;
	if(pl==pr){Max[p]=Min[p]=a[pl],cnt[p]=1,Mix[p]=nex[a[pl]]-a[pl];return;}
	int mid=pl+pr>>1;Build(p<<1,pl,mid);Build(p<<1|1,mid+1,pr);push_up(p);
}
inline void ca(int p,int ind){if(tag[p]) a[ind]=tag[p];a[ind]+=add[p];tag[p]=add[p]=0;}
inline void update1(int l,int r,int x,int p=1,int pl=1,int pr=n){
	if(l<=pl&&pr<=r){
		if(Mix[p]>=x){fa(p,x);return;}
		if(Max[p]==Min[p]){fc(p,Max[p]+x);return;}
	}int mid=pl+pr>>1;push_down(p);
	if(l<=mid) update1(l,r,x,p<<1,pl,mid);
	if(r>mid) update1(l,r,x,p<<1|1,mid+1,pr);
	push_up(p);
}
inline void update2(int l,int r,int x,int p=1,int pl=1,int pr=n){
	if(pl==pr){ca(p,pl);a[pl]*=x;fc(p,a[pl]);return;}
	if(l<=pl&&pr<=r&&Max[p]==Min[p]){fc(p,Max[p]*x);return;}
	int mid=pl+pr>>1;push_down(p);
	if(l<=mid) update2(l,r,x,p<<1,pl,mid);
	if(r>mid) update2(l,r,x,p<<1|1,mid+1,pr);
	push_up(p);
}
inline void update3(int l,int r,int x,int p=1,int pl=1,int pr=n){
	if(l<=pl&&pr<=r){fc(p,x);return;}
	int mid=pl+pr>>1;push_down(p);
	if(l<=mid) update3(l,r,x,p<<1,pl,mid);
	if(r>mid) update3(l,r,x,p<<1|1,mid+1,pr);
	push_up(p);
}
inline int ask(int l,int r,int p=1,int pl=1,int pr=n){
	if(l<=pl&&pr<=r) return !Mix[p]*cnt[p];
	push_down(p);int mid=pl+pr>>1;
	return (l<=mid?ask(l,r,p<<1,pl,mid):0)+(r>mid?ask(l,r,p<<1|1,mid+1,pr):0);
}
int main(){
	f[42]=f[424]=f[4242]=f[42424]=f[424242]=1;
	x=1e9;for(register int i=N-1;i;i--){if(f[i]) x=i;nex[i]=x;}
	n=read(),m=read();for(register int i=1;i<=n;i++) a[i]=read();
	Build();
	while(m--){
		op=read(),l=read(),r=read(),c=op<4?read():0;
		if(op==1) update1(l,r,c);
		else if(op==2){if(c^1) update2(l,r,c);}
		else if(op==3) update3(l,r,c);
		else write(ask(l,r)),putchar('\n');
	}
    return 0;
}