将每个点看成二维坐标点$(i,a_i)$，那么每次操作的范围都是一个矩形。
于是建立KD-Tree，通过打标记支持操作即可。
时间复杂度$O(m\sqrt{n})$。
#include<cstdio>
#include<algorithm>
const int N=50010,P=536870912;
int n,m,i,root,cmp_d,ans,op,A,B,C,D,E;
struct info{
int a,b;
info(){a=1,b=0;}
info(int _a,int _b){a=_a,b=_b;}
info operator+(info x){return info(1LL*x.a*a%P,(1LL*x.a*b+x.b)%P);}
}tmp;
struct node{
int d[2],l,r,Max[2],Min[2];
int cnt,val,sum;
info tag;
}T[N];
inline bool cmp(const node&a,const node&b){return a.d[cmp_d]<b.d[cmp_d];}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void umax(int&a,int b){if(a<b)a=b;}
inline void umin(int&a,int b){if(a>b)a=b;}
inline void up(int x){
T[x].cnt=1;
if(T[x].l){
T[x].cnt+=T[T[x].l].cnt;
umax(T[x].Max[0],T[T[x].l].Max[0]);
umin(T[x].Min[0],T[T[x].l].Min[0]);
umax(T[x].Max[1],T[T[x].l].Max[1]);
umin(T[x].Min[1],T[T[x].l].Min[1]);
}
if(T[x].r){
T[x].cnt+=T[T[x].r].cnt;
umax(T[x].Max[0],T[T[x].r].Max[0]);
umin(T[x].Min[0],T[T[x].r].Min[0]);
umax(T[x].Max[1],T[T[x].r].Max[1]);
umin(T[x].Min[1],T[T[x].r].Min[1]);
}
}
int build(int l,int r,int D){
int mid=(l+r)>>1;
cmp_d=D,std::nth_element(T+l+1,T+mid+1,T+r+1,cmp);
T[mid].Max[0]=T[mid].Min[0]=T[mid].d[0];
T[mid].Max[1]=T[mid].Min[1]=T[mid].d[1];
if(l!=mid)T[mid].l=build(l,mid-1,!D);
if(r!=mid)T[mid].r=build(mid+1,r,!D);
return up(mid),mid;
}
inline void tag(int x,info p){
T[x].val=(1LL*p.a*T[x].val+p.b)%P;
T[x].sum=(1LL*p.a*T[x].sum+1LL*p.b*T[x].cnt)%P;
T[x].tag=T[x].tag+p;
}
inline void pb(int x){
if(T[x].tag.a==1&&T[x].tag.b==0)return;
if(T[x].l)tag(T[x].l,T[x].tag);
if(T[x].r)tag(T[x].r,T[x].tag);
T[x].tag=info();
}
void change(int x){
if(T[x].Max[E]<A||T[x].Min[E]>B)return;
if(T[x].Min[E]>=A&&T[x].Max[E]<=B){tag(x,tmp);return;}
pb(x);
if(T[x].d[E]>=A&&T[x].d[E]<=B)T[x].val=(1LL*C*T[x].val+D)%P;
if(T[x].l)change(T[x].l);
if(T[x].r)change(T[x].r);
T[x].sum=(T[x].val+T[T[x].l].sum+T[T[x].r].sum)%P;
}
void ask(int x){
if(T[x].Max[E]<A||T[x].Min[E]>B)return;
if(T[x].Min[E]>=A&&T[x].Max[E]<=B){ans=(ans+T[x].sum)%P;return;}
pb(x);
if(T[x].d[E]>=A&&T[x].d[E]<=B)ans=(ans+T[x].val)%P;
if(T[x].l)ask(T[x].l);
if(T[x].r)ask(T[x].r);
T[x].sum=(T[x].val+T[T[x].l].sum+T[T[x].r].sum)%P;
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++)T[i].d[0]=i,read(T[i].d[1]);
root=build(1,n,0);
while(m--){
read(op),read(A),read(B),ans=0,E=op&1;
if(op<2)read(C),read(D),tmp=info(C%=P,D%=P);
if(op==0)change(root);
if(op==1)change(root);
if(op==2)ask(root),printf("%d\n",ans);
if(op==3)ask(root),printf("%d\n",ans);
}
return 0;
}