首页 > 代码库 > HDU3487(splay区间翻转+区间切割)

HDU3487(splay区间翻转+区间切割)

题意:开始有一个1,2,3,。。。n的序列,进行m次操作,cut a b c将区间[a,b]取出得到新序列,将区间插入到新序列第c个元素之后。filp a b 将区间a,b翻转,输出最终的序列。

思路:对于cut操作我们需要先提取出区间[a,b]然后,先暂时分裂出去,然后以c为边界分裂左右两部分,然后合并左边的和区间[a,b],将最大的旋转至根,然后和右边的合并。对于filp操作,我们可以使用lazy标记,先不翻转,需要的时候再翻转,代码如下

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. /************************************************************************* 
  2.     > File Name: A.cpp 
  3.     > Author: acvcla 
  4.     > QQ: 
  5.     > Mail: acvcla@gmail.com  
  6.     > Created Time: 2014年11月17日 星期一 23时34分13秒 
  7.  ************************************************************************/  
  8. #include<iostream>  
  9. #include<algorithm>  
  10. #include<cstdio>  
  11. #include<vector>  
  12. #include<cstring>  
  13. #include<map>  
  14. #include<queue>  
  15. #include<stack>  
  16. #include<string>  
  17. #include<cstdlib>  
  18. #include<ctime>  
  19. #include<set>  
  20. #include<math.h>  
  21. using namespace std;  
  22. typedef long long LL;  
  23. typedef pair<int,int>pii;  
  24. const int maxn = 3e5 + 10;  
  25. #define rep(i,a,b) for(int i=(a);i<=(b);i++)  
  26. #define pb push_back  
  27. int siz[maxn],rev[maxn],pre[maxn],ch[maxn][2],key[maxn],ans[maxn];  
  28. int tot,root,n;  
  29. inline void newnode(int &x,int fa,int k){  
  30.     x=++tot;  
  31.     pre[x]=fa;  
  32.     siz[x]=1;  
  33.     key[x]=k;  
  34.     ch[x][0]=ch[x][1]=rev[x]=0;  
  35. }  
  36. inline void Modify(int x){  
  37.     if(!x)return;  
  38.     rev[x]^=1;  
  39. }  
  40. inline void push_down(int x){  
  41.     if(x&&rev[x]){  
  42.         swap(ch[x][0],ch[x][1]);  
  43.         Modify(ch[x][0]);  
  44.         Modify(ch[x][1]);  
  45.         Modify(x);  
  46.     }  
  47. }  
  48. inline void push_up(int x){  
  49.     if(!x)return ;  
  50.     siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;  
  51. }  
  52. void built(int &x,int L,int R,int fa){  
  53.     if(L>R)return;  
  54.     int M=(L+R)>>1;  
  55.     newnode(x,fa,M);  
  56.     built(ch[x][0],L,M-1,x);  
  57.     built(ch[x][1],M+1,R,x);  
  58.     push_up(x);  
  59. }  
  60. void Rotate(int x,int kind){  
  61.     int y=pre[x];  
  62.     push_down(y);  
  63.     push_down(x);  
  64.   
  65.     ch[y][!kind]=ch[x][kind];  
  66.     pre[ch[x][kind]]=y;  
  67.     ch[x][kind]=y;  
  68.   
  69.     if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;  
  70.     pre[x]=pre[y];  
  71.     pre[y]=x;  
  72.   
  73.     push_up(y);  
  74.     push_up(x);  
  75. }  
  76. void Splay(int x,int goal){  
  77.     while(pre[x]!=goal){  
  78.         if(pre[pre[x]]==goal){  
  79.             Rotate(x,ch[pre[x]][0]==x);  
  80.         }else{  
  81.             int y=pre[x];  
  82.             int kind=(ch[pre[y]][0]==y);  
  83.             if(ch[y][kind]==x){  
  84.                 Rotate(x,!kind);  
  85.                 Rotate(x,kind);  
  86.             }else{  
  87.                 Rotate(y,kind);  
  88.                 Rotate(x,kind);  
  89.             }  
  90.         }  
  91.     }  
  92.     if(goal==0)root=x;  
  93. }  
  94. int Get_kth(int x,int k){  
  95.     push_down(x);  
  96.     int tz=siz[ch[x][0]]+1;  
  97.     if(tz==k)return x;  
  98.     if(tz>k)return Get_kth(ch[x][0],k);  
  99.     return Get_kth(ch[x][1],k-tz);  
  100. }  
  101. void init(int n){  
  102.     root=tot=siz[0]=pre[0]=ch[0][0]=ch[0][1]=rev[0]=0;  
  103.     newnode(root,0,-1);  
  104.     newnode(ch[root][1],root,n+1);  
  105.     built(ch[ch[root][1]][0],1,n,ch[root][1]);  
  106.     push_up(ch[root][1]);  
  107.     push_up(root);  
  108. }  
  109. int Get_max(int x){  
  110.     push_down(x);  
  111.     while(ch[x][1]){  
  112.         x=ch[x][1];  
  113.         push_down(x);  
  114.     }  
  115.     return x;  
  116. }  
  117. void merge(int root1,int root2)/*root2接到root1右子树,要求root1无右子树*/  
  118. {  
  119.     ch[root1][1]=root2;  
  120.     pre[root2]=root1;  
  121. }  
  122. int __;  
  123. void travel(int x){  
  124.     if(!x)return;  
  125.     push_down(x);  
  126.     travel(ch[x][0]);  
  127.     ans[__++]=key[x];  
  128.     travel(ch[x][1]);  
  129. }  
  130. int main(){  
  131.         int n,m;  
  132.         while(~scanf("%d%d",&n,&m)){  
  133.             if(n<0&&m<0)return 0;  
  134.             init(n);  
  135.             char op[10];  
  136.             int L,R,C;  
  137.             while(m--){  
  138.                 scanf("%s%d%d",op,&L,&R);  
  139.                 if(op[0]==‘F‘){  
  140.                     Splay(Get_kth(root,L),0);  
  141.                     Splay(Get_kth(root,R+2),root);  
  142.                     Modify(ch[ch[root][1]][0]);  
  143.                 }else{  
  144.                     scanf("%d",&C);  
  145.                     Splay(Get_kth(root,L),0);  
  146.                     Splay(Get_kth(root,R+2),root);  
  147.                     int root1=ch[ch[root][1]][0];/*删除区间[L,R]*/  
  148.                     ch[ch[root][1]][0]=0;  
  149.                     push_up(ch[root][1]);  
  150.                     push_up(root);  
  151.                     Splay(Get_kth(root,C+1),0);/*先分裂区间C两边,插入区间[L,R],然后合并*/  
  152.                     int root2=ch[root][1];  
  153.                     merge(root,root1);  
  154.                     push_up(root);  
  155.                     Splay(Get_max(root),0);  
  156.                     merge(root,root2);  
  157.                     push_up(root);  
  158.                 }  
  159.             }  
  160.             __=0;  
  161.             travel(root);  
  162.             rep(i,1,n)printf("%d%c",ans[i],i==n?‘\n‘:‘ ‘);  
  163.         }  
  164.         return 0;  

HDU3487(splay区间翻转+区间切割)