Splay 區間反轉

懶标記處理 向下傳時交換左右子樹

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
struct Node {int ls,rs,sum,flip,sz,fa,data;}t[N];
int a[N],num=,m,n,root=;
void pushdown(int k) {
    if(t[k].flip) {
        t[t[k].ls].flip^=;t[t[k].rs].flip^=;
        t[k].flip=;swap(t[k].ls,t[k].rs);
    }
}
void pushup(int k){
    t[k].sz=t[t[k].ls].sz+t[t[k].rs].sz+;
    t[k].sum=t[t[k].ls].sum+t[t[k].rs].sum+t[k].data;
}
void lturn(int x){
    int y=t[x].fa,z=t[y].fa;
    t[y].rs=t[x].ls;t[t[x].ls].fa=y;
    t[x].ls=y;t[y].fa=x;t[x].fa=z;
    if(t[z].ls==y) t[z].ls=x;
    else t[z].rs=x;
}
void rturn(int x){
    int y=t[x].fa,z=t[y].fa;
    t[y].ls=t[x].rs;t[t[x].rs].fa=y;
    t[x].rs=y;t[y].fa=x;t[x].fa=z;
    if(t[z].rs==y) t[z].rs=x;
    else t[z].ls=x;
}
void splay(int x,int f){
    while(t[x].fa!=f){
        int y=t[x].fa;
        pushdown(y);pushdown(x);
        if(t[y].ls==x) rturn(x);
        else if(t[y].rs==x) lturn(x);
        pushup(y);pushup(x);
    }
    if(f==) root=x;
}
void insert(int x){
    t[++num].data=x;t[num].sz=;t[num].sum=x;t[num].fa=root;
    t[num].ls=t[num].rs=;t[root].rs=num;
    splay(num,);pushup(num);
}
int getxth(int k,int x){
    pushdown(k);
    int wtf=t[t[k].ls].sz+;
    if(wtf==x) return k;
    if(wtf<x) return getxth(t[k].rs,x-wtf);
    if(wtf>x) return getxth(t[k].ls,x);
}
void reverse(int k,int x,int y){
    splay(getxth(root,x-),);splay(getxth(root,y+),root);
    t[t[t[root].rs].ls].flip^=;
}
int getsum(int k,int x,int y){
    splay(getxth(root,x-),);splay(getxth(root,y+),root);
    return t[t[t[root].rs].ls].sum;
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    insert();
    for(int i=;i<=n;i++) {
        scanf("%d",&a[i]);
        insert(a[i]);
    }
    insert();
    for(int i=;i<=m;i++){
        char s[];int x,y;
        scanf("%s%d%d",s,&x,&y);
        if(s[]=='R') reverse(root,x+,y+);
        if(s[]=='S') printf("%d\n",getsum(root,x+,y+));
    }
    return ;
}