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;
}