首页 > 代码库 > [Tyvj 1729] 文艺平衡树
[Tyvj 1729] 文艺平衡树
题面如下:
Tyvj 1729 文艺平衡树
Time Limit: 1 Sec Memory Limit: 128 MBDescription
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是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<=nOutput
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 31 31 31 4Sample Output
4 3 2 1 5
啊,又是一道板子题
题目要求支持的操作只有区间翻转,其中定位需要维护$size$,翻转要维护翻转标记,所以总体来说还是比较好写的.Splay写这题思路也很明确,每次Splay区间左/右端点的左/右边结点到根/根的右孩子,然后对根的右子结点的左子树打翻转标记即可w
直接贴代码w
GitHub
1 /********************************* 2 Judge Result:Accepted 3 4 *********************************/ 5 #include <cstdio> 6 #include <vector> 7 #include <cstring> 8 #include <cstring> 9 #include <iostream> 10 #include <algorithm> 11 12 #define lch chd[0] 13 #define rch chd[1] 14 #define kch chd[k] 15 #define xch chd[k^1] 16 17 const int INF=0x2FFFFFFF; 18 19 class SplayTree{ 20 private: 21 struct Node{ 22 int k; 23 int sz; 24 bool rev; 25 Node* prt; 26 Node* chd[2]; 27 Node(const int& key){ 28 this->k=key; 29 this->sz=1; 30 this->prt=NULL; 31 this->lch=NULL; 32 this->rch=NULL; 33 this->rev=false; 34 } 35 ~Node(){ 36 if(this->lch!=NULL) 37 delete this->lch; 38 if(this->rch!=NULL) 39 delete this->rch; 40 } 41 inline void Maintain(){ 42 if(this!=NULL) 43 this->sz=this->lch->size()+this->rch->size()+1; 44 } 45 inline void Swap(){ 46 if(this!=NULL){ 47 this->rev=!this->rev; 48 std::swap(this->lch,this->rch); 49 } 50 } 51 inline void PushDown(){ 52 if(this->rev){ 53 this->rev=false; 54 this->lch->Swap(); 55 this->rch->Swap(); 56 } 57 } 58 inline int key(){ 59 return this==NULL?0:this->k; 60 } 61 inline int size(){ 62 return this==NULL?0:this->sz; 63 } 64 }*root; 65 inline void Rotate(Node* root,int k){ 66 Node* tmp=root->xch; 67 root->PushDown(); 68 tmp->PushDown(); 69 tmp->prt=root->prt; 70 if(root->prt==NULL) 71 this->root=tmp; 72 else if(root->prt->lch==root) 73 root->prt->lch=tmp; 74 else 75 root->prt->rch=tmp; 76 root->xch=tmp->kch; 77 if(tmp->kch!=NULL) 78 tmp->kch->prt=root; 79 tmp->kch=root; 80 root->prt=tmp; 81 root->Maintain(); 82 tmp->Maintain(); 83 } 84 void Splay(Node* root,Node* prt=NULL){ 85 while(root->prt!=prt){ 86 int k=root->prt->lch==root; 87 if(root->prt->prt==prt){ 88 Rotate(root->prt,k); 89 } 90 else{ 91 int d=root->prt->prt->lch==root->prt; 92 Rotate(k==d?root->prt->prt:root->prt,k); 93 Rotate(root->prt,d); 94 } 95 } 96 } 97 Node* Build(const std::vector<int>& v,int l,int r){ 98 if(l>r) 99 return NULL;100 int mid=(l+r)>>1;101 Node* tmp=new Node(v[mid]);102 tmp->lch=Build(v,l,mid-1);103 tmp->rch=Build(v,mid+1,r);104 if(tmp->lch!=NULL)105 tmp->lch->prt=tmp;106 if(tmp->rch!=NULL)107 tmp->rch->prt=tmp;108 tmp->Maintain();109 return tmp;110 }111 void PrintTree(Node* root,int deep){112 for(int i=0;i<deep;i++)113 fputc(‘ ‘,stderr);114 fprintf(stderr, "(root=0x%X,key=%dsize=%d)\n", root,root->key(),root->size());115 if(root==NULL)116 return;117 PrintTree(root->lch,deep+1);118 PrintTree(root->rch,deep+1);119 }120 public:121 SplayTree(){122 this->root=new Node(-INF);123 this->root->rch=new Node(-INF);124 this->root->rch->prt=this->root;125 }126 SplayTree(const std::vector<int>& v){127 this->root=Build(v,0,v.size()-1);128 }129 ~SplayTree(){130 delete this->root;131 }132 Node* Kth(int pos){133 ++pos;134 Node* root=this->root;135 while(root!=NULL){136 root->PushDown();137 int k=root->lch->size()+1;138 if(pos<k)139 root=root->lch;140 else if(pos==k)141 return root;142 else{143 pos-=k;144 root=root->rch;145 }146 }147 return NULL;148 }149 inline void Reverse(const int& l,const int& r){150 this->Splay(this->Kth(l-1));151 this->Splay(this->Kth(r+1),this->root);152 this->root->rch->lch->Swap();153 this->root->rch->Maintain();154 this->root->Maintain();155 }156 inline void Insert(const int& pos,SplayTree* data){157 this->Splay(this->Kth(pos));158 this->Splay(this->Kth(pos+1),this->root);159 Node* tmp=data->root;160 data->root=NULL;161 this->root->rch->lch=tmp;162 tmp->prt=this->root->rch;163 this->root->rch->Maintain();164 this->root->Maintain();165 }166 void Print(){167 this->PrintTree(this->root,0);168 }169 };170 171 int FastRead();172 173 int main(){174 freopen("sph.in","r",stdin);175 freopen("sph.out","w",stdout);176 SplayTree* tree=new SplayTree();177 std::vector<int> v;178 int n=FastRead();179 int m=FastRead();180 int a,b;181 for(int i=1;i<=n;i++){182 v.push_back(i);183 }184 tree->Insert(0,new SplayTree(v));185 for(int i=0;i<m;i++){186 a=FastRead();187 b=FastRead();188 tree->Reverse(a,b);189 }190 for(int i=1;i<=n;i++){191 printf("%d ",tree->Kth(i)->key());192 }193 putchar(‘\n‘);194 return 0;195 }196 197 int FastRead(){198 int ans=0;199 bool neg=false;200 register char ch=getchar();201 while(!isdigit(ch)){202 if(ch==‘-‘)203 neg=true;204 ch=getchar();205 }206 while(isdigit(ch)){207 ans=ans*10+ch-‘0‘;208 ch=getchar();209 }210 if(neg)211 ans=-ans;212 return ans;213 }
然后放图~
[Tyvj 1729] 文艺平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。