题目：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；

详细可以看这个博客：

注意一下处理 rev 标记和 lzy 标记，顺序是先 reverse 再 add，更改 rev 标记时要把 lzy 标记取反；

调了一上午：

1.各种计算 sum 时，上限原来写的是20，又觉得不好，改成 len，然而应该是 min(len,20) ...

2.query 写得不好的话会 TLE ... 还是模仿了 Narh 的写法，感觉很优秀。

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #define mid ((l+r)>>1)using namespace std;typedef long long ll;int const xn=5e4+5,mod=19940417;int n,q,cnt=1,a[xn],lzy[xn<<1],ans[xn];ll c[xn][25];bool rev[xn<<1];char ch;struct N{
   int ls,rs,len; ll sum[25];}t[xn<<1];int rd(){    int ret=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=0; ch=getchar();}    while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();    return f?ret:-ret;}void init(){    for(int i=0;i<=n;i++)c[i][0]=1;    for(int i=1;i<=n;i++)        for(int j=1;j<=min(i,20);j++)            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}ll pls(ll a,ll b){a=a+b; while(a>=mod)a-=mod; while(a<0)a+=mod; return a;}void pushup(int x){    int ls=t[x].ls,rs=t[x].rs,lm=min(t[x].len,20);    for(int i=1;i<=lm;i++)//min!!     {        t[x].sum[i]=0;        for(int j=0;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,20);    for(int i=lm;i>=1;i--)//min          for(int j=1,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,20);    for(int i=1;i<=lm;i+=2)t[x].sum[i]=pls(mod,-t[x].sum[i]);//min    rev[x]^=1;    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]=0;    if(lzy[x])ad(ls,lzy[x]),ad(rs,lzy[x]),lzy[x]=0;}void build(int x,int l,int r){    t[x].sum[0]=1; t[x].len=r-l+1;    if(l==r){t[x].sum[1]=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+1,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
         
          =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
          
           =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&&r<=R) { int lm=min(k,r-l+1); for(int i=k;i>=0;i--) for(int j=1;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
            
             >ch; a=rd(); b=rd(); if(ch!='R')c=rd(); if(ch=='I')c=pls(c,0),add(1,1,n,a,b,c); if(ch=='R')reverse(1,1,n,a,b); if(ch=='Q')// printf("%lld\n",query(1,1,n,a,b,c)%mod); { for(int i=1;i<=c;i++)ans[i]=0; query(1,1,n,a,b,c); printf("%d\n",ans[c]); } } return 0;}