【データ構造SPLAY】splay区間が反転し、区間とクエリー、区間が挿入され、区間が削除され、区間が修正されます.

#include
#include
#include
#define maxn (200005)
using namespace std;
int ch[maxn][2],val[maxn],size[maxn],f[maxn];
int root,tot,n,m,a[maxn],add[maxn],sum[maxn];
bool flip[maxn];
//ch[i][1]    i    
//ch[i][0]    i    
//flip[i]    i                  
//val[i]    i      
//size[i]    i         （    ）
//a[i]         
//add[i]    i lazy(   lazy      )
//sum[i]    i       （    ）
//f[i]    i   
inline void pushup(int x)//   pushup         
//  pushup    pushup  
{
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
    sum[x]+=add[ch[x][0]]*size[ch[x][0]]+add[ch[x][1]]*size[ch[x][1]];
}
inline void pushdown(int x)//     
//  pushdown    pushdown  
{
    if (flip[x]!=0)
    {
        flip[ch[x][0]]^=1;
        flip[ch[x][1]]^=1;
        swap(ch[x][0],ch[x][1]);//               
        flip[x]=0;
    }
    if(ch[x][0]) add[ch[x][0]]+=add[x];
    if(ch[x][1]) add[ch[x][1]]+=add[x];
    val[x]+=add[x];
    add[x]=0;
}
inline int is(int x)//  x f[x]      
{
    return ch[f[x]][1]==x;
}
inline void link(int y,int x,int d)// x  y d  
{
    if (x) f[x]=y;
    ch[y][d]=x;
        if (x) pushup(x);
    pushup(y);

}
inline void newnode(int &x,int fa,int v)//   
{
    //&x        x              x           x  
    tot++;
    x=tot;
    f[x]=fa;
    val[x]=v;
    if  (fa==0)
    x=0;
    pushup(x);
    pushup(fa);
}
inline void rotate(int x,int d)
// x d   ， x      
{
    int y=f[x];
    int z=f[y];
    pushdown(z);
    pushdown(y);
    pushdown(x);
    link(y,ch[x][!d],d);
    if (z) link(z,x,is(y));
    f[x]=z;
    link(x,y,!d);
    if (z) pushup(z);
}
inline void zig(int x)// x         
{
    rotate(x,1);
}
inline void zag(int x)// x         
{
    rotate(x,0);
}
inline void splay(int x,int goal=0)// x   goal   
//   int goal=0        goal     ，   goal  0  
// goal=0   x      
{
    pushdown(x);
    while (f[x]!=goal)
    {
        int y=f[x];
        int z=f[y];
        if (z==goal)
        {
            rotate(x,is(x));
            break;
        }
        if (ch[z][1]==y)
        {
            if (ch[y][1]==x) zig(y),zig(x);
            //   zig(x),zig(x)         ，  
            else zag(x),zig(x);
        }
        else
        {
            if (ch[y][0]==x) zag(y),zag(x);
            else zig(x),zag(x);
        }
        pushup(x);
    }
    if (goal==0) root=x;
    pushup(x);
    if (goal) pushup(goal);
}
inline int pre(int x)// x   
{
    splay(x);
    x=ch[x][1];
    while(ch[x][0]) x=ch[x][0];
    return x;
}
inline int nex(int x)// x   
{
    splay(x);
    x=ch[x][0];
    while(ch[x][1]) x=ch[x][1];
    return x;
}
inline void insert(int v)//             ，          v   
{
    int x=root;
    while(ch[x][vinline int getnum(int k,int x)//      k      (    )
{
    pushdown(x);
    if (x) pushup(x);
    if(size[ch[x][1]]+1==k) return x;
    else if (size[ch[x][1]]+1return getnum(k-size[ch[x][1]]-1,ch[x][0]);
    else return getnum(k,ch[x][1]);
}
inline int build(int l,int r)// (l,r)     
{
    if (l>r) return 0;

    tot++;
    int t=tot;
    int mid=(l+r)/2;
    val[t]=a[mid];

    link(t,build(l,mid-1),1);
    link(t,build(mid+1,r),0);

    return t;
}
inline void insert_line(int k,int num)//  k      num   
{
    for (int i=1;i<=num;i++)
    scanf("%d",&a[i]);
    if (root==0)
    {
        root=build(1,num);
        return ;
    }
    int totk;
    if (k)  totk=getnum(k,root);
    else totk=getnum(1,root);
    int nexk=nex(totk);
    if (nexk==0)
    link(totk,build(1,num),0);
    else
    {
        splay(totk);
        splay(nexk,totk);
        if (k==0)
        link(totk,build(1,num),1);
        else
        link(nexk,build(1,num),1);
    }
}
inline void del(int l,int r)//    [l,r]
{
    l=getnum(l,root);
    r=getnum(r,root);
    int prel=pre(l);
    int nexr=nex(r);
    if (prel==0&&nexr==0)
    root=0;
    else if (prel==0)
    splay(nexr),ch[nexr][1]=0,pushup(nexr);
    else if (nexr==0)
    splay(prel),ch[prel][0]=0,pushup(prel);
    else 
    {
        splay(prel);
        splay(nexr,prel);
        ch[nexr][1]=0;
        pushup(nexr);
    }
}
inline void rev(int l,int r)//    [l,r]
{
    l=getnum(l,root);
    r=getnum(r,root);   
    int prel=pre(l);
    int nexr=nex(r);

    if (prel==0&&nexr==0)
    flip[root]^=1;
    else if (prel==0)
    {
        splay(nexr);
        flip[ch[nexr][1]]^=1;
    }
    else if (nexr==0)
    {
        splay(prel);
        flip[ch[prel][0]]^=1;
    }
    else
    {
        splay(prel);
        splay(nexr,prel);
        flip[ch[nexr][1]]^=1;
        pushup(nexr);
    }
}
inline void addv(int l,int r,int v)//   [l,r]     v
{
    l=getnum(l,root);
    r=getnum(r,root);
    int prel=pre(l);
    int nexr=nex(r);
    if (prel==0&&nexr==0)
    add[root]+=v;
    else if (prel==0)
    {
        splay(nexr);
        add[ch[nexr][1]]+=v;
    }
    else if (nexr==0)
    {
        splay(prel);
        add[ch[prel][0]]+=v;
    }
    else
    {
        splay(prel);
        splay(nexr,prel);
        add[ch[nexr][1]]+=v;
    }
}
inline int query(int l,int r)//    [l,r]  
{
    l=getnum(l,root);
    r=getnum(r,root);
    int prel=pre(l);
    int nexr=nex(r);
    if (prel==0&&nexr==0)
    printf("%d
",sum[root]);
    else if (prel==0)
    {
        splay(nexr);
        printf("%d
",sum[ch[nexr][1]]);
    }
    else if (nexr==0)
    {
        splay(prel);
        printf("%d
",sum[ch[prel][0]]);
    }
    else
    {
        splay(prel);
        splay(nexr,prel);
        printf("%d
",sum[ch[nexr][1]]);    
    }
}
//void putt()//       
//{
//  for (int i=1;i<=tot;i++)
//  cout<
//}
int main()
{   
    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)
    scanf("%d",&a[i]);

    root=build(1,n);
    f[root]=0;
//      for (int j=1;j<=20;j++)
//      cout<
//      cout<
    for (int i=1;i<=m;i++)
    {
//      putt();
//      cout<
        char c;
        int a,b,lps;
        cin>>c>>a>>b;   
        if (c=='R')
        rev(a,b);
        else if (c=='D')
        del(a,b);
        else if (c=='I')
        insert_line(a,b);
        else if (c=='A')
        scanf("%d",&lps),addv(a,b,lps);
        else 
        query(a,b);

//      for (int j=1;j<=20;j++)
//      cout<
//      cout<
//      cout<
    }
}