---恢复内容开始---
又是一道裸数据结构题。
之前受序列操作的蛋疼写法影响，只用一个tag，不知道怎么记，之后看了下别人的，终于领悟要用两个tag，一个add,一个mul，维护相当简单，想清楚就行。
简单说下解法。
add mul就是一般的将[L,R]split出来然后打tag.
mulx：我将[L,R+1]split出来，然后这一段split成l:[L,R-1],mid:[R,R],r[R+1,R+1]，然后把mid的系数加到r上，把mid的系数赋为0，然后merge(mid,l,r);这里注意如果L==R将会出现问题，于是这里我特判了一下。
还是就是见乘就得加long long.....
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int Maxn=+,Mod=,MaxR=;
int _a[Maxn],cnt;
inline void fadd(int&a,int b){
a+=b;if(a>Mod)a-=Mod;
}
struct node{
int v,sz,add,mul;//itself isn't in it
node*ch[];
node(){
sz=v=add=;mul=;
}
inline void maintain(){
sz=ch[]->sz+ch[]->sz+;
}
inline int cmp(int k){
if(ch[]->sz+==k)return -;
return k>ch[]->sz+;
}
inline void AddTag(int Add,int Mul){
v=(long long)v*Mul%Mod;
fadd(v,Add);
mul=(long long)mul*Mul%Mod;//注意long long
add=(long long)add*Mul%Mod;//注意long long
fadd(add,Add);
}
inline void down(){
ch[]->AddTag(add,mul);
ch[]->AddTag(add,mul);
add=;mul=;
}
}da[Maxn],*root,*null;int tot;
inline void rotate(node*&o,int d){
node*t=o->ch[d];
o->ch[d]=t->ch[d^];
t->ch[d^]=o;
o->maintain();
(o=t)->maintain();
}
void splay(node*&o,int k){
o->down();
int d=o->cmp(k);
if(d==-)return;
if(d)k-=o->ch[]->sz+;
node*&p=o->ch[d];
p->down();
int d2=p->cmp(k);
if(d2!=-){
if(d2)k-=p->ch[]->sz+;
splay(p->ch[d2],k);
if(d2!=d)rotate(p,d2);
else rotate(o,d);
}
rotate(o,d);
}
void build(node*&o,int l,int r){
if(l>r){
o=null;
return;
}
int mid=(l+r)>>;
o=da+ ++tot;
build(o->ch[],l,mid-);
build(o->ch[],mid+,r);
o->maintain();
}
void print(node*o){
if(o==null)return;
o->down();
print(o->ch[]);
++cnt;
if(cnt>= && cnt<=MaxR+)_a[cnt-]=o->v;
// printf("%d\n",o->v);
print(o->ch[]);
}
inline int calc(int x,const int*a){
int ret=a[MaxR];
for(int i=MaxR;i>=;i--){
ret=(long long)ret*x%Mod;
fadd(ret,a[i]);
}
return ret;
}
inline void split(node*o,int k,node*&l,node*&r){
splay(o,k);
r=o->ch[];
(l=o)->ch[]=null;
l->maintain();
}
inline node*merge(node*l,node*r){
splay(l,l->sz);
l->ch[]=r;
l->maintain();
return l;
}
int get_tp(char *opt){
if(opt[]=='a')return ;
if(opt[]=='m')return opt[]?:;
return ;
}
int main(){
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout); int tp,L,R,V,n;
null=da;
null->ch[]=null->ch[]=null;
build(root,,MaxR+);
node*o,*l,*r,*mid;
char opt[]={};
for(scanf("%d\n",&n);n--;){
scanf("%s",opt);
tp=get_tp(opt);
if(tp<=){
scanf("%d%d%d",&L,&R,&V);V%=Mod;
split(root,L+,l,o);
split(o,R-L+,mid,r);
if(tp==)mid->AddTag(V,);
else mid->AddTag(,V);
root=merge(merge(l,mid),r);
}
else if(tp==){
scanf("%d%d",&L,&R);
split(root,L+,l,o);
split(o,R-L+,mid,r);
if(R==L){//这里必须特判
splay(mid,);
mid->down();
mid->ch[]->down();
fadd(mid->ch[]->v,mid->v);
mid->v=;
}else{
node*_o,*_l,*_r,*_mid;
split(mid,mid->sz-,_l,_o);
split(_o,,_mid,_r);
_mid->down();
_r->down();
fadd(_r->v,_mid->v);
_mid->v=;
mid=merge(merge(_mid,_l),_r);
}
root=merge(merge(l,mid),r);
}
else {
scanf("%d",&V);V%=Mod;
cnt=;
print(root);
printf("%d\n",calc(V,_a));
}
} return ;
}