3223: Tyvj 1729 文藝平衡樹

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?6881??Solved:?4213
[Submit][Status][Discuss]

Description

您需要寫一種數據結構（可參考題目標題），來維護一個有序數列，其中需要提供以下操作：翻轉一個區間，例如原有序序列是5?4?3?2?1，翻轉區間是[2,4]的話，結果是5?2?3?4?1?

Input

第一行為n,m?n表示初始序列有n個數，這個序列依次是(1,2……n-1,n)??m表示翻轉操作次數
接下來m行每行兩個數[l,r]?數據保證?1<=l<=r<=n??

Output

?

輸出一行n個數字，表示原始序列經過m次變換后的結果?

?

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

?

N,M<=100000

?

?

?

模板題，區間翻轉問題

延時標記的作用是優化，如果一個區間翻轉之后再翻轉回來，用延時標記就可以優化，不必再翻轉。比如翻轉[1,4]，再翻轉[1,4]，就可以延時標記優化。

其他的代碼里寫了注釋。

?

代碼:

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<bitset> 6 #include<cassert> 7 #include<cctype> 8 #include<cmath> 9 #include<cstdlib> 10 #include<ctime> 11 #include<deque> 12 #include<iomanip> 13 #include<list> 14 #include<map> 15 #include<queue> 16 #include<set> 17 #include<stack> 18 #include<vector> 19 using namespace std; 20 typedef long long ll; 21 22 const double PI=acos(-1.0); 23 const double eps=1e-6; 24 const ll mod=1e9+7; 25 const int inf=0x3f3f3f3f; 26 const int maxn=1e5+10; 27 const int maxm=100+10; 28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 29 30 /* 31 將當前排名為l-1 +1 的節點轉到根 32 將當前排名為r+2的節點轉到根的右子樹的根節點 33 則根的右子樹的根節點的左子樹為所求區間 34 直接打標記就可以了 35 */ 36 37 int n,m,sz,rt,pre[maxn],l,r,ch[maxn][2],data[maxn],size[maxn],rev[maxn]; 38 39 //在爸爸節點打上標記，然后進行下放，如果進行了兩次相反的翻轉，lazy標記就會消失，這樣就減少了翻轉次數達到優化 40 41 void pushup(int k)//要先pushup兒子才能pushup爸爸 42 { 43 size[k]=size[ch[k][0]]+size[ch[k][1]]+1;//當前節點的size為左子樹+右子樹+自己 44 } 45 46 void pushdown(int k)//要先pushdown爸爸才能pushdown兒子 47 { 48 int l=ch[k][0],r=ch[k][1];//左兒子和右兒子 49 if(rev[k]){//翻轉區間 50 swap(ch[k][0],ch[k][1]);//翻轉左右兒子 51 rev[l]^=1;rev[r]^=1;//標記下傳 52 rev[k]=0;//當前節點標記去掉 53 } 54 } 55 56 void rotate(int x,int &k)//翻轉操作 57 { 58 int y=pre[x],z=pre[y],l,r; 59 if(ch[y][0]==x) l=0; 60 else l=1; 61 r=l^1; 62 if(y==k) k=x; 63 else{if(ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;} 64 pre[x]=z;pre[y]=x;pre[ch[x][r]]=y; 65 ch[y][l]=ch[x][r];ch[x][r]=y; 66 pushup(y);pushup(x); 67 } 68 69 void splay(int x,int &k)//splay到目標狀態 70 { 71 while(x!=k){ 72 int y=pre[x],z=pre[y]; 73 if(y!=k){ 74 if(ch[y][0]==x^ch[z][0]==y)rotate(x,k); 75 else rotate(y,k); 76 } 77 rotate(x,k); 78 } 79 } 80 81 int find(int k,int rank) 82 { 83 pushdown(k);//有標記就pushdown 84 int l=ch[k][0],r=ch[k][1]; 85 if(size[l]+1==rank) return k; 86 else if(size[l]>=rank) return find(l,rank); 87 else return find(r,rank-size[l]-1); 88 } 89 90 void change(int l,int r) 91 { 92 int x=find(rt,l),y=find(rt,r+2); 93 splay(x,rt);splay(y,ch[x][1]); 94 int z=ch[y][0]; 95 rev[z]^=1; 96 } 97 98 void build(int l,int r,int f) 99 { 100 if(l>r) return; 101 int now=data[l],last=data[f]; 102 if(l==r){ 103 pre[now]=last; 104 size[now]=1; 105 if(l<f) ch[last][0]=now; 106 else ch[last][1]=now; 107 return; 108 } 109 110 int mid=(l+r)>>1; 111 now=data[mid]; 112 build(l,mid-1,mid); 113 build(mid+1,r,mid); 114 pre[now]=last; 115 pushup(mid); 116 if(mid<f) ch[last][0]=now; 117 else ch[last][1]=now; 118 } 119 120 int main() 121 { 122 scanf("%d%d",&n,&m); 123 for(int i=1;i<=n+2;i++) 124 data[i]=++sz; 125 build(1,n+2,0);//建樹，建兩個哨兵節點為1，n+2。 126 rt=(n+3)>>1;//中點為rt 127 for(int i=1;i<=m;i++){ 128 scanf("%d%d",&l,&r); 129 change(l,r); 130 } 131 for(int i=2;i<=n+1;i++) 132 printf("%d ",find(rt,i)-1);//去掉哨兵節點 133 return 0; 134 }

?

?

?

先貼個板子，有的操作并不理解，過幾天再看。

?

轉載于:https://www.cnblogs.com/ZERO-/p/9610440.html

總結

以上是生活随笔為你收集整理的BZOJ 3223: Tyvj 1729 文艺平衡树-Splay树(区间翻转)模板题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。