题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2962
维护 sum[i] 表示选 i 个的乘积和，合并两个子树就枚举两边选多少，乘起来即可；
取反只需要把奇数个数的乘积和变成相反数即可；
关键是区间 + k：比如对于一个元素，原来是 a, b, c，+ k 变成 (a+k), (b+k), (c+k)
从每个括号里选 a,b,c 或者 k，如果选 j 个 k ，那么就是 sum[i] += sum[i-j] * k^j * C(len-(i-j), j)，组合数表示从剩余的位置中选 j 个 k；
详细可以看这个博客：https://blog.csdn.net/qq_35866453/article/details/77998472
注意一下处理 rev 标记和 lzy 标记，顺序是先 reverse 再 add，更改 rev 标记时要把 lzy 标记取反；
调了一上午：
1.各种计算 sum 时，上限原来写的是20，又觉得不好，改成 len，然而应该是 min(len,20) ...
2.query 写得不好的话会 TLE ... 还是模仿了 Narh 的写法，感觉很优秀。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
int const xn=5e4+,mod=;
int n,q,cnt=,a[xn],lzy[xn<<],ans[xn];
ll c[xn][];
bool rev[xn<<];
char ch;
struct N{int ls,rs,len; ll sum[];}t[xn<<];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return f?ret:-ret;
}
void init()
{
for(int i=;i<=n;i++)c[i][]=;
for(int i=;i<=n;i++)
for(int j=;j<=min(i,);j++)
c[i][j]=(c[i-][j]+c[i-][j-])%mod;
}
ll pls(ll a,ll b){a=a+b; while(a>=mod)a-=mod; while(a<)a+=mod; return a;}
void pushup(int x)
{
int ls=t[x].ls,rs=t[x].rs,lm=min(t[x].len,);
for(int i=;i<=lm;i++)//min!!
{
t[x].sum[i]=;
for(int j=;j<=i;j++)
t[x].sum[i]=pls(t[x].sum[i],(t[ls].sum[j]*t[rs].sum[i-j])%mod);
}
}
void ad(int x,int k)
{
int len=t[x].len,lm=min(len,);
for(int i=lm;i>=;i--)//min
for(int j=,pw=k;j<=i;j++,pw=((ll)pw*k)%mod)//
t[x].sum[i]=pls(t[x].sum[i],t[x].sum[i-j]*pw%mod*c[len-i+j][j]%mod);
lzy[x]=pls(lzy[x],k);
}
void re(int x)
{
int lm=min(t[x].len,);
for(int i=;i<=lm;i+=)t[x].sum[i]=pls(mod,-t[x].sum[i]);//min
rev[x]^=;
lzy[x]=pls(mod,-lzy[x]);
}
void pushdown(int x)
{
int ls=t[x].ls,rs=t[x].rs;
if(rev[x])re(ls),re(rs),rev[x]=;
if(lzy[x])ad(ls,lzy[x]),ad(rs,lzy[x]),lzy[x]=;
}
void build(int x,int l,int r)
{
t[x].sum[]=; t[x].len=r-l+;
if(l==r){t[x].sum[]=a[l]; return;}
t[x].ls=++cnt; t[x].rs=++cnt;
int ls=t[x].ls,rs=t[x].rs;
build(ls,l,mid); build(rs,mid+,r);
pushup(x);
}
void add(int x,int l,int r,int L,int R,int k)
{
if(l>=L&&r<=R){ad(x,k); return;}
pushdown(x);
int ls=t[x].ls,rs=t[x].rs;
if(mid>=L)add(ls,l,mid,L,R,k);
if(mid<R)add(rs,mid+,r,L,R,k);
pushup(x);
}
void reverse(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R){re(x); return;}
pushdown(x);
int ls=t[x].ls,rs=t[x].rs;
if(mid>=L)reverse(ls,l,mid,L,R);
if(mid<R)reverse(rs,mid+,r,L,R);
pushup(x);
}
/*
ll query(int x,int l,int r,int L,int R,int k)
{
int ls=t[x].ls,rs=t[x].rs;
if(l>=L&&r<=R)return t[x].sum[k];
pushdown(x);
if(mid>=R)return query(ls,l,mid,L,R,k);
else if(mid<L)return query(rs,mid+1,r,L,R,k);
else
{
ll ret=0;
for(int i=0;i<=k;i++)
ret=pls(ret,query(ls,l,mid,L,R,i)*query(rs,mid+1,r,L,R,k-i)%mod);
return ret;
}
}
*/
void query(int cr,int l,int r,int L,int R,int k)
{
if(l>=L&&r<=R)
{
int lm=min(k,r-l+);
for(int i=k;i>=;i--)
for(int j=;j<=lm&&j<=i;j++)//j<=i
ans[i]=((ll)ans[i]+t[cr].sum[j]*ans[i-j])%mod;
return;
} pushdown(cr);
if(L<=mid) query(t[cr].ls,l,mid,L,R,k);
if(mid<R) query(t[cr].rs,mid+,r,L,R,k);
} int main()
{
n=rd(); q=rd();
init();
for(int i=;i<=n;i++)a[i]=rd();
build(,,n);
ans[]=;
for(int i=,a,b,c;i<=q;i++)
{
cin>>ch;
a=rd(); b=rd();
if(ch!='R')c=rd();
if(ch=='I')c=pls(c,),add(,,n,a,b,c);
if(ch=='R')reverse(,,n,a,b);
if(ch=='Q')
// printf("%lld\n",query(1,1,n,a,b,c)%mod); {
for(int i=;i<=c;i++)ans[i]=;
query(,,n,a,b,c);
printf("%d\n",ans[c]);
} }
return ;
}