Play with Chain

Time Limit: 6000/2000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)

【Problem Description】 YaoYao is fond of playing his chains. He has a chain containing n diamonds on it. Diamonds are numbered from 1 to n. At first, the diamonds on the chain is a sequence: 1, 2, 3, …, n. He will perform two types of operations: CUT a b c: He will first cut down the chain from the ath diamond to the bth diamond. And then insert it after the cth diamond on the remaining chain. For example, if n=8, the chain is: 1 2 3 4 5 6 7 8; We perform “CUT 3 5 4”, Then we first cut down 3 4 5, and the remaining chain would be: 1 2 6 7 8. Then we insert “3 4 5” into the chain before 5th diamond, the chain turns out to be: 1 2 6 7 3 4 5 8.
FLIP a b: We first cut down the chain from the ath diamond to the bth diamond. Then reverse the chain and put them back to the original position. For example, if we perform “FLIP 2 6” on the chain: 1 2 6 7 3 4 5 8. The chain will turn out to be: 1 4 3 7 6 2 5 8
He wants to know what the chain looks like after perform m operations. Could you help him? 【Input】 There will be multiple test cases in a test data. For each test case, the first line contains two numbers: n and m (1≤n, m≤3*100000), indicating the total number of diamonds on the chain and the number of operations respectively. Then m lines follow, each line contains one operation. The command is like this: CUT a b c?? // Means a CUT operation, 1 ≤ a ≤ b ≤ n, 0≤ c ≤ n-(b-a+1). FLIP a b????// Means a FLIP operation, 1 ≤ a < b ≤ n. The input ends up with two negative numbers, which should not be processed as a case. 【Output】 For each test case, you should print a line with n numbers. The ith number is the number of the ith diamond on the chain. 【Sample Input】 8 2 CUT 3 5 4 FLIP 2 6 -1 -1

【Sample Output】

1 4 3 7 6 2 5 8

?

【題意】

給出一列數，然后對整個數列執行兩種操作：切下一段插入到另外的位置，或者把其中的一整段整個翻轉一下。

求經過一系列操作之后，數列最后的樣子。

?

【分析】

數據范圍最高能夠到達3e5那么大，因此算法至少要是O(nlogn)復雜度以下才可能達到要求。

考慮采用Splay解決（這樣的題目只能用這種動態維護的樹結構不是么？）

?

初始先建樹，把1~n加入Splay樹。由于數列在后面是要被打亂順序的，Splay二叉平衡樹的性質只有在初始的時候是被保持的，之后是靠size，即每個點在中序遍歷中的位置來維護。最后輸出數列則只需要中序遍歷一遍即可。

切割操作：若要切下a~b段，則把第a-1個結點移到根，把第b+1個結點移到根以下（即跟的右子樹），則整個a~b段就落在b+1的左子樹上，切出來。插入到c的時候，將c移到根，c+1移到根的右子樹，則切出來的插入到c+1的左子樹即可

翻轉操作：用上面相同的方法把a~b整合到一棵子樹上，然后可以參考線段樹標記的方法，通過標記來完成訪問結點的翻轉等操作。

具體可以在紙上模擬一下......

?

【教訓】

教訓還是比較慘痛的...卡在這道題上好久了。

首先是輸入輸出以后要特別注意結尾方式，兩個負數結尾還是兩個-1結尾

把各種可能出現的不同情況考慮完整

?

1 /* *********************************************** 2 MYID : Chen Fan 3 LANG : G++ 4 PROG : HDU3487 5 ************************************************ */ 6 7 #include <iostream> 8 #include <cstdio> 9 #include <cstring> 10 #include <algorithm> 11 12 using namespace std; 13 14 #define MAXN 300010 15 16 int sons[MAXN][2]; 17 int father[MAXN],size[MAXN],data[MAXN],list[MAXN]; 18 bool flag[MAXN]; 19 int spt=0,spttail=0; 20 21 void down(int x) 22 { 23 if (flag[x]) 24 { 25 flag[x]=0; 26 swap(sons[x][0],sons[x][1]); 27 flag[sons[x][0]]^=1; 28 flag[sons[x][1]]^=1; 29 } 30 } 31 32 void rotate(int x,int w) //rotate(node,0/1) 33 { 34 int y=father[x]; 35 down(y);down(x); 36 sons[y][!w]=sons[x][w]; 37 if (sons[x][w]) father[sons[x][w]]=y; 38 39 father[x]=father[y]; 40 if (father[y]) sons[father[y]][y==sons[father[y]][1]]=x; 41 42 sons[x][w]=y; 43 father[y]=x; 44 45 size[x]=size[y]; 46 size[y]=size[sons[y][0]]+size[sons[y][1]]+1; 47 } 48 49 void splay(int x,int y) //splay(node,position) 50 { 51 down(x); 52 while(father[x]!=y) 53 { 54 if (father[father[x]]==y) rotate(x,x==sons[father[x]][0]); 55 else 56 { 57 int t=father[x]; 58 int w=(sons[father[t]][0]==t); 59 if (sons[t][w]==x) 60 { 61 rotate(x,!w); 62 rotate(x,w); 63 } else 64 { 65 rotate(t,w); 66 rotate(x,w); 67 } 68 } 69 } 70 if (!y) spt=x; 71 } 72 73 void select(int x,int v,int p) //select(root,k,position) 74 { 75 down(x); 76 while(v!=size[sons[x][0]]+1) 77 { 78 if (v<=size[sons[x][0]]) 79 { 80 x=sons[x][0]; 81 down(x); 82 } 83 else 84 { 85 v-=size[sons[x][0]]+1; 86 x=sons[x][1]; 87 down(x); 88 } 89 } 90 splay(x,p); 91 } 92 93 bool done=false; 94 95 void outp(int x) 96 { 97 down(x); 98 if (sons[x][0]) outp(sons[x][0]); 99 if (done) printf(" "); 100 done=true; 101 printf("%d",data[x]); 102 if (sons[x][1]) outp(sons[x][1]); 103 } 104 105 void maketree(int l,int r) 106 { 107 spttail++; 108 int now=spttail,w=(l+r)/2,ls=0,rs=0; 109 data[now]=w; 110 flag[now]=false; 111 sons[now][0]=0; 112 sons[now][1]=0; 113 114 if (l<=w-1) 115 { 116 ls=spttail+1; 117 sons[now][0]=ls; 118 father[ls]=now; 119 maketree(l,w-1); 120 } 121 if (w+1<=r) 122 { 123 rs=spttail+1; 124 sons[now][1]=rs; 125 father[rs]=now; 126 maketree(w+1,r); 127 } 128 129 size[now]=size[ls]+size[rs]+1; 130 } 131 132 int main() 133 { 134 freopen("3487.txt","r",stdin); 135 136 int n,m; 137 scanf("%d%d",&n,&m); 138 while(!(n<0&&m<0)) 139 { 140 spt=1; 141 spttail=0; 142 father[1]=0; 143 maketree(1,n); 144 145 for (int i=1;i<=m;i++) 146 { 147 char s[10]; 148 scanf("%s",&s); 149 if (s[0]=='C') 150 { 151 int a,b,c,temp; 152 scanf("%d%d%d",&a,&b,&c); 153 154 if (a>1) 155 { 156 select(spt,a-1,0); 157 if (b<n) 158 { 159 select(spt,b+1,spt); 160 temp=sons[sons[spt][1]][0]; 161 sons[sons[spt][1]][0]=0; 162 size[spt]-=size[temp]; 163 size[sons[spt][1]]-=size[temp]; 164 } else 165 { 166 temp=sons[spt][1]; 167 sons[spt][1]=0; 168 size[spt]-=size[temp]; 169 } 170 } else 171 { 172 if (b<n) 173 { 174 select(spt,b+1,0); 175 temp=sons[spt][0]; 176 sons[spt][0]=0; 177 size[spt]-=size[temp]; 178 } else temp=spt; 179 } 180 181 if (c>0) 182 { 183 select(spt,c,0); 184 if (c==size[spt]) 185 { 186 sons[spt][1]=temp; 187 father[temp]=spt; 188 size[spt]+=size[temp]; 189 } else 190 { 191 select(spt,c+1,spt); 192 sons[sons[spt][1]][0]=temp; 193 father[temp]=sons[spt][1]; 194 size[spt]+=size[temp]; 195 size[sons[spt][1]]+=size[temp]; 196 } 197 } else 198 { 199 if (spt!=temp) 200 { 201 select(spt,1,0); 202 sons[spt][0]=temp; 203 father[temp]=spt; 204 size[spt]+=size[temp]; 205 } 206 } 207 } else 208 { 209 int a,b,temp; 210 scanf("%d%d",&a,&b); 211 if (a>1) 212 { 213 select(spt,a-1,0); 214 if (b<n) 215 { 216 select(spt,b+1,spt); 217 temp=sons[sons[spt][1]][0]; 218 } else 219 { 220 temp=sons[spt][1]; 221 } 222 } else 223 { 224 if (b<n) 225 { 226 select(spt,b+1,0); 227 temp=sons[spt][0]; 228 } else temp=spt; 229 } 230 flag[temp]^=1; 231 } 232 } 233 done=false; 234 outp(spt); 235 printf("\n"); 236 scanf("%d%d",&n,&m); 237 } 238 239 return 0; 240 } View Code

?

?

?

轉載于:https://www.cnblogs.com/jcf94/p/4374315.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的HDU 3487 Play with Chain | Splay的全部內容，希望文章能夠幫你解決所遇到的問題。

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