rt，很朴素的线段树了，最后一个包还有两三个点过不去

能否放宽点时限

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
#define pc putchar
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define mo 998244353
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
const int N=1000005;
int n,q,a[N],X=3,sum[N<<2],mn[N<<2],mi[N];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+(ch^48);ch=getchar();}
    return ret*ff;
}
void write(int x){if(x<0){x=-x,pc('-');}if(x>9) write(x/10);pc(x%10+48);}
void writeln(int x){write(x),hh;}
void writesp(int x){write(x),pc(' ');}
inline int add(int x,int y){
    x+=y;
    if(x>=mo) x-=mo;
    return x;
}
void build(int l,int r,int k){
    if(l==r){
        sum[k]=mi[a[l]];
        mn[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(k));
    build(mid+1,r,rs(k));
    sum[k]=add(sum[ls(k)],sum[rs(k)]);
    mn[k]=min(mn[ls(k)],mn[rs(k)]);
}
void update(int l,int r,int x,int v,int k){
    if(l==r){
        sum[k]=mi[v];
        mn[k]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(l,mid,x,v,ls(k));
    else update(mid+1,r,x,v,rs(k));
    sum[k]=add(sum[ls(k)],sum[rs(k)]);
    mn[k]=min(mn[ls(k)],mn[rs(k)]);
}
int query(int l,int r,int x,int y,int k){
    if(x<=l&&r<=y) return mn[k];
    int mid=(l+r)>>1,res=1e9;
    if(x<=mid) res=min(res,query(l,mid,x,y,ls(k)));
    if(mid+1<=y) res=min(res,query(mid+1,r,x,y,rs(k)));
    return res;
}
int queryX(int l,int r,int x,int y,int k){
    if(x<=l&&r<=y) return sum[k];
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res=add(res,queryX(l,mid,x,y,ls(k)));
    if(mid+1<=y) res=add(res,queryX(mid+1,r,x,y,rs(k)));
    return res;
}
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    mi[0]=1;
    for(int i=1;i<=1e6;i++) mi[i]=1ll*mi[i-1]*X%mo;
    build(1,n,1);
    while(q--){
        int opt=read();
        if(opt==0){
            int x=read(),v=read();
            update(1,n,x,v,1);
        }
        else{
            int l1=read(),r1=read(),l2=read(),r2=read();
            int mn1=query(1,n,l1,r1,1),mn2=query(1,n,l2,r2,1);
            int sx1=queryX(1,n,l1,r1,1),sx2=queryX(1,n,l2,r2,1);
            if(mn1<mn2){
                if(1ll*sx1*mi[mn2-mn1]%mo==sx2) puts("YES");
                else puts("NO");
            }
            else{
                if(1ll*sx2*mi[mn1-mn2]%mo==sx1) puts("YES");
                else puts("NO");
            }
        }
    }
    return 0;
}