求问有关本题的空间问题

#include <bits/stdc++.h>
using namespace std;
constexpr int N=50005;
constexpr int mod=19940417;
int c[N][25];
int n,m;
namespace DS{
	int a[N];
	struct STree{
		struct tag{
			int add,inv;
			tag(){
				add=inv=0;
			}
			void reset(){
				add=inv=0;
			}
			tag operator +(const tag &x)const{
				tag ans;
				if(!inv&&!x.inv){
					ans.add=((add+x.add)%mod+mod)%mod;
					ans.inv=0;
					return ans;
				}
				if(!inv&&x.inv){
					ans.add=((add+x.add)%mod+mod)%mod;
					ans.inv=1;
					return ans;
				}
				if(inv&&!x.inv){
					ans.add=((add-x.add)%mod+mod)%mod;
					ans.inv=1;
					return ans;
				}
				if(inv&&x.inv){
					ans.add=((add-x.add)%mod+mod)%mod;
					ans.inv=0;
					return ans;
				}
			}
		}laz[N<<2];
		struct node{
			int l,r;
			int val[25];
			node(){
				l=r=0;
				memset(val,0,sizeof(val));
				val[0]=1;
			}
			node operator +(const node &x)const{
				node ans;
				ans.l=l;ans.r=x.r;
				int len1=r-l+1;
				int len2=x.r-x.l+1;
				for(int i=0;i<=min(20,len1);i++)
					for(int j=0;j<=min(20,len2);j++){
						if(!i&&!j) continue;
						if(i+j<=20)
							ans.val[i+j]=(ans.val[i+j]+1ll*val[i]*x.val[j]%mod)%mod;
					}
				return ans;
			}
			node operator +(const tag &x)const{
				node ans;
				ans.l=l;ans.r=r;
				int len=r-l+1;
				int tmp[25];
				tmp[0]=1;
				for(int i=1;i<=20;i++) tmp[i]=1ll*tmp[i-1]*x.add%mod;
//				v_i->v_j*c(n-j,i-j)*x^{i-j}
				for(int i=min(len,20);i;i--){
					for(int j=i;~j;j--){
						ans.val[i]+=1ll*val[j]*c[len-j][i-j]%mod*tmp[i-j]%mod;
						ans.val[i]%=mod;
//						cout<<endl;
//						cout<<l<<" "<<r<<" "<<i<<" "<<j<<endl;
//						cout<<ans.val[i]<<" "<<val[j]<<" "<<c[len-j][i-j]<<" "<<tmp[i-j]<<" "<<x.add<<endl;
//						cout<<endl;
					}
				}
//				for(int i=min(len,20);i;i--){
//					int cur=0; asdfasdfasdfas
// sr & jj mjj
//					for(int j=0;j<i;j++){
//						cur+=1ll*val[j]*tmp[i-j]%mod*c[len-j][i-j]%mod;
//						cur%=mod;
//					}
//					ans.val[i]=(val[i]+cur)%mod;
//				}
				if(x.inv){
					for(int i=1;i<=min(20,len);i+=2){
						ans.val[i]=-ans.val[i];
						ans.val[i]%=mod;
						ans.val[i]+=mod;
						ans.val[i]%=mod;
					}
				}
				return ans;
			}
		} tr[N<<2];
		void build(int pos,int l,int r){
			if(l==r){
				tr[pos].l=tr[pos].r=l;
				tr[pos].val[1]=a[l];
				return ;
			}
			int mid=l+((r-l)>>1);
			build(pos<<1,l,mid);
			build(pos<<1|1,mid+1,r);
			tr[pos]=tr[pos<<1]+tr[pos<<1|1];
		}
		void change(int pos,tag x){
			tr[pos]=tr[pos]+x;
			laz[pos]=laz[pos]+x;
		}
		void pushdown(int pos){
			change(pos<<1,laz[pos]);
			change(pos<<1|1,laz[pos]);
			laz[pos].reset();
		}
		void update(int pos,int l,int r,int cl,int cr,tag x){
			if(l>=cl&&r<=cr){
				change(pos,x);
				return ;
			}
			pushdown(pos);
			int mid=l+((r-l)>>1);
			if(cl<=mid) update(pos<<1,l,mid,cl,cr,x);
			if(cr>mid) update(pos<<1|1,mid+1,r,cl,cr,x);
			tr[pos]=tr[pos<<1]+tr[pos<<1|1];
		}
		node query(int pos,int l,int r,int ql,int qr){
			if(l>=ql&&r<=qr) return tr[pos];
			pushdown(pos);
			int mid=l+((r-l)>>1);
			if(qr<=mid) return query(pos<<1,l,mid,ql,qr);
			if(ql>mid) return query(pos<<1|1,mid+1,r,ql,qr);
			return query(pos<<1,l,mid,ql,qr)+query(pos<<1|1,mid+1,r,ql,qr);
		}
		void print(int pos,int l,int r){
			cout<<pos<<" "<<l<<" "<<r<<endl;
			for(int i=0;i<=20;i++) cout<<tr[pos].val[i]<<" ";cout<<endl;
			if(l==n) cout<<endl;
			if(l==r) return ;
			pushdown(pos);
			int mid=l+((r-l)>>1);
			print(pos<<1,l,mid);
			print(pos<<1|1,mid+1,r);
		}
//		static_print_laz
		void static_print_laz(int pos,int l,int r){
			cout<<pos<<" "<<l<<" "<<r<<" "<<laz[pos].add<<" "<<laz[pos].inv<<endl;
			if(l==n) cout<<endl;
			if(l==r) return ;
			pushdown(pos);
			int mid=l+((r-l)>>1);
			static_print_laz(pos<<1,l,mid);
			static_print_laz(pos<<1|1,mid+1,r);
		}
	};
}
DS::STree tr;
signed main(){
//	freopen("test.out","w",stdout);
	// freopen("test1.in","r",stdin);
	// freopen("test1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>DS::a[i];
	c[0][0]=1;
	for(int i=1;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	tr.build(1,1,n);
	while(m--){
		char op;cin>>op;
		if(op=='I'){
			int l,r,x;cin>>l>>r>>x;
			x%=mod;
			x+=mod;
			x%=mod;
			DS::STree::tag k;
			k.add=x;
			k.inv=0;
			tr.update(1,1,n,l,r,k);
		}
		if(op=='R'){
			int l,r;cin>>l>>r;
			DS::STree::tag k;
			k.add=0;
			k.inv=1;
			tr.update(1,1,n,l,r,k);
		}
		if(op=='Q'){
			int l,r,k;cin>>l>>r>>k;
			cout<<(tr.query(1,1,n,l,r).val[k]%mod+mod)%mod<<'\n';
		}
//		tr.static_print_laz(1,1,n);
//		tr.print(1,1,n);
	}
	return 0;
}