題目背景
這是一道經典的Splay模板題——文藝平衡樹。
題目描述
您需要寫一種數據結構，來維護一個有序數列，其中需要提供以下操作：翻轉一個區間，例如原有序序列是5 4 3 2 1，翻轉區間是[2,4]的話，結果是5 2 3 4 1
輸入輸出格式
輸入格式：
?
第一行為n,m(n,m<=100000) n表示初始序列有n個數，這個序列依次是(1,2, \cdots n-1,n)(1,2,?n?1,n)?m表示翻轉操作次數
接下來m行每行兩個數?[l,r][l,r]?數據保證?1 \leq l \leq r \leq n1≤l≤r≤n
?
輸出格式：
?
輸出一行n個數字，表示原始序列經過m次變換后的結果
輸入輸出樣例
輸入樣例
5 3
1 3
1 3
1 4 輸出樣例
4 3 2 1 5
splay模板題，維護該序列的中序遍歷不變，然后每次通過旋轉節點使操作的區間變作一顆字樹，然后打上標記即可。
什么是splay?
一棵伸展樹......
什么是伸展樹？
最近剛學，我個人的理解，大概就是一個能在不破壞二叉搜索樹結構(即中序遍歷始終為升序)的情況下
通過旋轉一個節點到他根節點位置使得操作區間恰好全部位于一棵子樹內的方法。
然后就打上標記，之后在類似線段樹一樣的pushdown傳遞信息就好了。
代碼如下：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define mod #define mid (R+L>>1) #define M 2000010 using namespace std; LL read(){LL nm=0,oe=1;char cw=getchar();while(!isdigit(cw)) oe=cw=='-'?-oe:oe,cw=getchar();while(isdigit(cw)) nm=nm*10+(cw-'0'),cw=getchar();return nm*oe; } LL n,m,l[M],r[M],tp[M],ad,sz[M],tg[M],ace,a,b,p,q,cnt; bool flag=false; void pushdown(LL x){if(tg[x]==0) return;tg[x]=0,swap(l[x],r[x]);tg[l[x]]^=1,tg[r[x]]^=1; } void pushup(LL x){sz[x]=sz[l[x]]+sz[r[x]]+1;} LL build(LL L,LL R,LL rt){if(L>R) return 0;tp[mid]=rt,sz[mid]=1;if(L==R) return L;l[mid]=build(L,mid-1,mid);r[mid]=build(mid+1,R,mid);sz[mid]+=sz[l[mid]]+sz[r[mid]];return mid; } void rotate(LL x){if(ace==x) return;LL top=tp[x];pushdown(top),pushdown(x);if(top==ace) ace=x,tp[x]=n+1,tp[top]=x;else{if(l[tp[top]]==top) l[tp[top]]=x;else r[tp[top]]=x;tp[x]=tp[top],tp[top]=x;}if(l[top]==x) l[top]=r[x],tp[r[x]]=top,r[x]=top;else r[top]=l[x],tp[l[x]]=top,l[x]=top;pushup(top),pushup(x); } void oper(LL x){if(x==ace||tp[x]==ace){return;}LL top=tp[x];pushdown(top);if(tp[top]==ace) rotate(x);else if(l[l[tp[top]]]==x||r[r[tp[top]]]==x) rotate(top);else rotate(x); } LL find(LL x,LL pos){pushdown(x);if(sz[l[x]]==pos-1) return x;if(sz[l[x]]<pos-1) return find(r[x],pos-sz[l[x]]-1);else return find(l[x],pos); } void ans(LL x){if(x==0) return;pushdown(x);ans(l[x]);if(x<n&&x>1){if(flag) printf(" ");flag=true;printf("%lld",x-1);}ans(r[x]); } int main(){n=read()+2,m=read(),ace=build(1,n,n+1);while(m--){a=read(),b=read();p=find(ace,a),q=find(ace,b+2);while(tp[q]!=ace&&q!=ace) oper(q);if(q!=ace) rotate(q);while(tp[p]!=ace) oper(p);tg[r[p]]^=1;}ans(ace);return 0; }
我這里還是寫的比較模糊，我也是通過了解別人的博客才理解了splay
就是這個 ->?http://blog.csdn.net/skydec/article/details/20151805
