小 Y 的数字

· · 题解

考虑势能线段树，要维护的有：区间最大值（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;
}