題目連結：https://www.nowcoder.com/acm/contest/141/C
時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
Special Judge, 64bit IO Format: %lld
題目描述
Eddy likes to play cards game since there are always lots of randomness in the game. For most of the cards game, the very first step in the game is shuffling the cards. And, mostly the randomness in the game is from this step. However, Eddy doubts that if the shuffling is not done well, the order of the cards is predictable!
To prove that, Eddy wants to shuffle cards and tries to predict the final order of the cards. Actually, Eddy knows only one way to shuffle cards that is taking some middle consecutive cards and put them on the top of rest. When shuffling cards, Eddy just keeps repeating this procedure. After several rounds, Eddy has lost the track of the order of cards and believes that the assumption he made is wrong. As Eddy's friend, you are watching him doing such foolish thing and easily memorizes all the moves he done. Now, you are going to tell Eddy the final order of cards as a magic to surprise him.
Eddy has showed you at first that the cards are number from 1 to N from top to bottom.
For example, there are 5 cards and Eddy has done 1 shuffling. He takes out 2-nd card from top to 4-th card from top(indexed from 1) and put them on the top of rest cards. Then, the final order of cards from top will be [2,3,4,1,5].
輸入描述:
Output one line contains N space-separated integers indicating the final order of the cards from top to bottom. 示例1
輸入
5 1
2 3 輸出
2 3 4 1 5 示例2
5 2
2 3
2 3 3 4 1 2 5 示例3
5 3
2 3
1 4
2 4 3 4 1 5 2 題意：
給出一個1~n的數字序列，給出m次操作，每次操作會将以第p個數字為開始的連續s個數字拿出來放到整個序列的開頭，求m次操作完成後的序列。
題解：
用splay來搞區間問題：javascript:void(0)
可以直接先區間移動的函數，也可以使用三次區間反轉來完成區間移動。
AC代碼：
#include<bits/stdc++.h>
#define Key_value ch[ch[root][1]][0]
using namespace std;
const int maxn=1e5+10;
int n,m;
/******************************** splay - st ********************************/
int root,nodecnt;
int par[maxn],ch[maxn][2];
int key[maxn],size[maxn];
bool rev[maxn];
void NewNode(int &x,int p,int k)
{
x=++nodecnt;
par[x]=p;
ch[x][0]=ch[x][1]=0;
key[x]=k;
size[x]=1;
rev[x]=0;
}
void Update_Rev(int x)
{
if(x==0) return;
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
void Pushup(int x)
{
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void Pushdown(int x)
{
if(rev[x])
{
Update_Rev(ch[x][0]);
Update_Rev(ch[x][1]);
rev[x]=0;
}
}
void Rotate(int x,int type) //旋轉，0為左旋zag，1為右旋zig
{
int y=par[x];
Pushdown(y); Pushdown(x); //先把y的标記向下傳遞,再把x的标記往下傳遞
ch[y][!type]=ch[x][type]; par[ch[x][type]]=y;
if(par[y]) ch[par[y]][(ch[par[y]][1]==y)]=x;
par[x]=par[y];
ch[x][type]=y; par[y]=x;
Pushup(y); Pushup(x);
}
void Splay(int x,int goal)
{
while(par[x]!=goal)
{
if(par[par[x]]==goal) Rotate(x,ch[par[x]][0]==x); //左孩子zig，有孩子zag
else
{
Pushdown(par[par[x]]); Pushdown(par[x]); Pushdown(x);
int y=par[x];
int type=(ch[par[y]][0]==y); //type=0，y是右孩子；type=1，y是左孩子
if(ch[y][type]==x)
{
Rotate(x,!type);
Rotate(x,type);
}
else
{
Rotate(y,type);
Rotate(x,type);
}
}
}
if(goal==0) root=x;
}
int Get_Kth(int x,int k) //得到第k個節點
{
Pushdown(x);
int t=size[ch[x][0]]+1;
if(t==k) return x;
if(t>k) return Get_Kth(ch[x][0],k);
else return Get_Kth(ch[x][1],k-t);
}
int Get_Min(int x)
{
Pushdown(x);
while(ch[x][0])
{
x=ch[x][0];
Pushdown(x);
}
return x;
}
int Get_Max(int x)
{
Pushdown(x);
while(ch[x][1])
{
x=ch[x][1];
Pushdown(x);
}
return x;
}
void Build(int &x,int l,int r,int par) //建樹，先建立中間結點，再建兩端的方法
{
if(l>r) return;
int mid=(l+r)/2;
NewNode(x,par,mid);
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Pushup(x);
}
void Init() //初始化，前後各加一個空節點
{
root=nodecnt=0;
ch[root][0]=ch[root][1]=size[root]=key[root]=par[root]=rev[root]=0;
NewNode(root,0,-1); //頭部加入一個空位
NewNode(ch[root][1],root,-1); //尾部加入一個空位
Build(Key_value,1,n,ch[root][1]);
Pushup(ch[root][1]);
Pushup(root);
}
void Move(int l,int r,int p) //截取[l,r]放到位置p之後
{
Splay(Get_Kth(root,l-1+1),0); //l的前驅l-1伸展到根
Splay(Get_Kth(root,r+1+1),root); //r的後繼r+1伸展到根的右孩子
int tmp=Key_value; //Key_value=ch[ch[root][1]][0]所統領的子樹即[l,r]
Key_value=0; //剝離[l,r]子樹
Pushup(ch[root][1]); Pushup(root);
Splay(Get_Kth(root,p+0+1),0); //p伸展到根
Splay(Get_Kth(root,p+1+1),root); //p的後繼p+1伸展到根的右孩子
Key_value=tmp; par[Key_value]=ch[root][1]; //接上[l,r]子樹
Pushup(ch[root][1]); Pushup(root);
}
void Reverse(int l,int r) //反轉[l,r]區間
{
Splay(Get_Kth(root,l-1+1),0);
Splay(Get_Kth(root,r+1+1),root);
Update_Rev(Key_value);
Pushup(ch[root][1]);
Pushup(root);
}
/******************************** splay - ed ********************************/
int tot;
void Inorder(int x)
{
if(x==0) return;
Pushdown(x);
Inorder(ch[x][0]);
tot++;
if(tot>=2 && tot<=n+1)
{
if(tot>2) printf(" ");
printf("%d",key[x]);
}
Inorder(ch[x][1]);
}
int main()
{
scanf("%d%d",&n,&m);
Init();
for(int i=1,st,ed;i<=m;i++)
{
scanf("%d%d",&st,&ed); ed=st+ed-1;
if(i%2) Move(st,ed,0);
else
{
Reverse(1,st-1);
Reverse(st,ed);
Reverse(1,ed);
}
}
Inorder(root);
printf("\n");
}