提交时间:2024-10-02 14:05:32

运行 ID: 32887

#include<bits/stdc++.h> #define int long long using namespace std; int n,a[200005],q; struct node{ int sz,j,o,jmn,omn; }; node operator+(node x,node y){ node res; res.sz=x.sz+y.sz; if(x.sz&1)res.j=x.j+y.o,res.o=x.o+y.j,res.jmn=min(x.jmn,y.omn),res.omn=min(x.omn,y.jmn); else res.j=x.j+y.j,res.o=x.o+y.o,res.jmn=min(x.jmn,y.jmn),res.omn=min(x.omn,y.omn); return res; } node operator+(node x,int y){ node res; res=x; res.o+=res.sz/2*y; res.j+=res.sz/2*y; if(res.sz)res.j+=y; res.jmn+=y; return res; } node t[800005]; int lz[800005],lzj[800005]; #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r>>1) void pu(int p){ t[p]=t[ls]+t[rs]; } void bd(int l,int r,int p){ if(l==r){ t[p].sz=1; t[p].j=a[l]; t[p].o=0; t[p].jmn=a[l]; return; } bd(l,mid,ls),bd(mid+1,r,rs); pu(p); return; } void pd(int p){ t[ls]=t[ls]+lz[p],t[rs]=t[rs]+lz[p]; lz[ls]+=lz[p],lz[rs]+=lz[p]; lz[p]=0; return; } void upd(int l,int r,int ml,int mr,int x,int p){ if(ml<=l&&r<=mr){ t[p]=t[p]+x; lz[p]+=x; return; } pd(p); if(mid>=ml)upd(l,mid,ml,mr,x,ls); if(mid+1<=mr)upd(mid+1,r,ml,mr,x,rs); pu(p); return; } node qu(int l,int r,int ml,int mr,int p){ if(ml<=l&&r<=mr)return t[p]; pd(p); node res={0,0,0}; if(mid>=ml)res=res+qu(l,mid,ml,mr,ls); if(mid+1<=mr)res=res+qu(mid+1,r,ml,mr,rs); return res; } signed main(){ //freopen("apple.in","r",stdin); //freopen("apple.out","w",stdout); cin>>n; for(int i=1;i<=n;i++)cin>>a[i],a[i]--; bd(1,n,1); cin>>q; while(q--){ int op,l,r,x; cin>>op>>l>>r; if(op==1){ cin>>x; upd(1,n,l,r,x,1); } else{ node res=qu(1,n,l,r,1); if(res.j==res.o&&res.jmn>=0&&res.omn>=0)cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }