C++11(clang++ 3.9) 解法, 执行用时: 486ms, 内存消耗: 5600K, 提交时间: 2019-03-09 18:00:31

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1000010
#define SIZE 100010
#define P 20130426
#define LL long long
#define GET (ch>='0'&&ch<='9')
using namespace std;
int n,x,y,v;
char ch[10];
int root,cnt;
LL ans;
inline void in(int &x)
{
    char ch=getchar();x=0;
    while (!GET)    ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();
}
struct splay
{
    int ch[2],fa,size;
    LL val,add,mul;
}tree[MAXN];
inline void push_up(int x)
{
    tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;
}
inline void push_down(int x)
{
    if (!x) return;
    if (tree[x].add==0&&tree[x].mul==1) return;
    int l=tree[x].ch[0],r=tree[x].ch[1];
    ((tree[l].val*=tree[x].mul)+=tree[x].add)%=P;
    ((tree[l].add*=tree[x].mul)+=tree[x].add)%=P;
    (tree[l].mul*=tree[x].mul)%=P;
    ((tree[r].val*=tree[x].mul)+=tree[x].add)%=P;
    ((tree[r].add*=tree[x].mul)+=tree[x].add)%=P;
    (tree[r].mul*=tree[x].mul)%=P;
    tree[x].add=0;tree[x].mul=1;
}
inline void rot(int x,int &f)
{
    int y=tree[x].fa,z=tree[y].fa,l,r;
    l=(tree[y].ch[1]==x);r=l^1;
    if (y==f)   f=x;
    else    tree[z].ch[tree[z].ch[1]==y]=x;
    tree[tree[x].ch[r]].fa=y;tree[y].fa=x;tree[x].fa=z;
    tree[y].ch[l]=tree[x].ch[r];tree[x].ch[r]=y;
    push_up(y);push_up(x);
}
inline void Splay(int x,int &f)
{
    while (x!=f)
    {
        int y=tree[x].fa,z=tree[y].fa;
        if (y!=f)   
        {
            if ((tree[y].ch[0]==x)^(tree[z].ch[0]==y))  rot(x,f);
            else    rot(y,f);
        }
        rot(x,f);
    }
}
inline int find(int x,int k)
{
    push_down(x);
    int l=tree[x].ch[0],r=tree[x].ch[1];
    if (tree[l].size+1==k)  return x;
    if (tree[l].size>=k)    return find(l,k);
    else    return find(r,k-tree[l].size-1);
}
inline void split(int l,int r)
{
    x=find(root,l);y=find(root,r);
    Splay(x,root);Splay(y,tree[x].ch[1]);
}
inline void calc(int x)
{
    if (!x) return;
    push_down(x);
    calc(tree[x].ch[1]);
    if (x!=1)   ans=(ans*v+tree[x].val)%P;
    calc(tree[x].ch[0]);
}
inline void build(int l,int r,int f)
{
    if (l>r)    return;
    int mid=(l+r)>>1;
    tree[mid].fa=f;tree[f].ch[mid>f]=mid;
    tree[mid].size=1;tree[mid].add=0;tree[mid].mul=1;
    if (l==r)   return;
    build(l,mid-1,mid);build(mid+1,r,mid);
    push_up(mid);
}
int main()
{
    in(n);int L,R,V;
    build(1,SIZE,0);root=(1+SIZE)>>1;cnt=SIZE;
    while (n--)
    {
        scanf("%s",ch);
        if (ch[0]=='m'&&ch[3]!='x')
        {
            in(L);in(R);L++;R++;in(V);V%=P;
            split(L,R+2);int now=tree[y].ch[0];
            (tree[now].val*=V)%=P;(tree[now].add*=V)%=P;(tree[now].mul*=V)%=P;
            push_up(y);push_up(x);
        }
        if (ch[0]=='a')
        {
            in(L);in(R);L++;R++;in(V);V%=P;
            split(L,R+2);int now=tree[y].ch[0];
            (tree[now].val+=V)%=P;(tree[now].add+=V)%=P;
            push_up(y);push_up(x);
        }
        if (ch[3]=='x')
        {
            in(L);in(R);L++;R++;
            split(R,R+3);int now1=tree[y].ch[0],now2=tree[now1].ch[0]+tree[now1].ch[1];
            push_down(x);push_down(y);push_down(now1);
            tree[now1].val+=tree[now2].val;tree[now1].size=1;
            tree[now2].fa=tree[now1].ch[0]=tree[now1].ch[1]=0;
            push_up(y);push_up(x);
            split(L,L+1);
            tree[y].ch[0]=++cnt;tree[cnt].size=1;
            tree[cnt].val=0;tree[cnt].fa=y;tree[cnt].add=0;tree[cnt].mul=1;
            push_up(y);push_up(x);
        }
        if (ch[0]=='q')
        {
            ans=0;in(v);v%=P;
            calc(root);printf("%lld\n",ans);
        }
    }
}