區間反轉 先發代碼 待會再談感悟

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define rep(i,l,r) for(int i=l;i<r;i++) 7 #define clr(a,x) memset(a,x,sizeof(a)) 8 using namespace std; 9 const int maxn=100005,maxm=100005; 10 int n,m; 11 struct node*null,*pt; 12 struct node{ 13 node*ch[2]; 14 int v,s; 15 bool rev; 16 node(int v1=0):v(v1),s(1),rev(0){ 17 ch[0]=ch[1]=null; 18 } 19 inline int cmp(int k)const{ 20 k-=ch[0]->s; 21 if(k==1) return -1; 22 return k<=0?0:1; 23 } 24 inline void update(){ 25 s=ch[0]->s+ch[1]->s+1; 26 } 27 inline void pushdown(){ 28 if(rev){ 29 rev=0; 30 swap(ch[0],ch[1]); 31 ch[0]->rev^=1; 32 ch[1]->rev^=1; 33 } 34 } 35 void*operator new(size_t){ 36 return pt++; 37 } 38 }; 39 node*root; 40 node x[maxn]; 41 void rotate(node*&o,int d) 42 { 43 node* k=o->ch[d^1]; 44 o->ch[d^1]=k->ch[d]; 45 k->ch[d]=o; 46 o->update(); 47 k->update(); 48 o=k; 49 } 50 void splay(node*&o,int k) 51 { 52 o->pushdown(); 53 int d=o->cmp(k); 54 if(d==-1) return; 55 if(d==1) k-=o->ch[0]->s+1; 56 node*p=o->ch[d]; 57 p->pushdown(); 58 int d2=p->cmp(k); 59 int k2=d2?k-p->ch[0]->s-1:k; 60 if(d2!=-1){ 61 splay(p->ch[d2],k2); 62 d==d2?rotate(o,d^1):rotate(o->ch[d],d); 63 } 64 rotate(o,d^1); 65 } 66 node*build(int l,int r) 67 { 68 if(l>=r) return null; 69 int mid=(l+r)>>1; 70 node*o=new node(mid); 71 if(l<mid) o->ch[0]=build(l,mid); 72 if(r>mid+1) o->ch[1]=build(mid+1,r); 73 o->update(); 74 return o; 75 } 76 void init() 77 { 78 pt=x; 79 null=new node(); 80 null->s=0; 81 root=build(0,n+2); 82 } 83 void dfs(node*o) 84 { 85 if(o==null) return; 86 o->pushdown(); 87 dfs(o->ch[0]); 88 if(o->v>=1&&o->v<=n) printf("%d ",o->v); 89 dfs(o->ch[1]); 90 } 91 int read() 92 { 93 int ans=0,f=1; 94 char c; 95 c=getchar(); 96 while(!isdigit(c)){ 97 if(c=='-') f=-1; 98 c=getchar(); 99 } 100 while(isdigit(c)){ 101 ans=ans*10+c-'0'; 102 c=getchar(); 103 } 104 return f*ans; 105 } 106 int main() 107 { 108 n=read(); 109 m=read(); 110 init(); 111 while(m--){ 112 int l=read(),r=read(); 113 if(l==r) continue; 114 splay(root,l); 115 splay(root->ch[1],r+1-root->ch[0]->s); 116 root->ch[1]->ch[0]->rev^=1; 117 } 118 dfs(root); 119 return 0; 120 } View Code

3223: Tyvj 1729 文藝平衡樹

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?1848??Solved:?1026
[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

?

Source

平衡樹

[Submit][Status][Discuss]

轉載于:https://www.cnblogs.com/chensiang/p/4618456.html

總結

以上是生活随笔為你收集整理的bzoj3223 splay的全部內容，希望文章能夠幫你解決所遇到的問題。

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