首页 > 代码库 > UVA 11922 Splay区间翻转+分裂+合并
UVA 11922 Splay区间翻转+分裂+合并
Description
Permutation Transformer
| Permutation Transformer |
Write a program to transform the permutation 1, 2, 3,..., n according to m instructions. Each instruction (a, b) means to take out the subsequence from the a-th to the b-th element, reverse it, then append it to the end.
Input
There is only one case for this problem. The first line contains two integers n and m ( 1
n, m100, 000). Each of the next m lines contains an instruction consisting of two integers a and b ( 1abn).
Output
Print n lines, one for each integer, the final permutation.
Explanation of the sample below
Instruction (2,5): Take out the subsequence {2,3,4,5}, reverse it to {5,4,3,2}, append it to the remaining permutation {1,6,7,8,9,10}
Instruction (4,8): The subsequence from the 4-th to the 8-th element of {1,6,7,8,9,10,5,4,3,2} is {8,9,10,5,4}. Take it out, reverse it, and you‘ll get the sample output.
Warning: Don‘t use cin, cout for this problem, use faster i/o methods e.g scanf, printf.
Sample Input
10 2 2 5 4 8
Sample Output
1 6 7 3 2 4 5 10 9 8
对序列进行m次操作，每次将[L,R]区间翻转后移到尾部。
提取区间之后翻转,分裂，进行两次合并
代码：
/*************************************************************************
> File Name: Spaly.cpp
> Author: acvcla
> QQ:
> Mail: acvcla@gmail.com
> Created Time: 2014Äê11ÔÂ16ÈÕ ÐÇÆÚÈÕ 00ʱ14·Ö26Ãë
************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 100;
const int inf=1e9+7;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
int ch[maxn][2],pre[maxn],rev[maxn],siz[maxn];
int root,tot;
int key[maxn];
void newnode(int &x,int fa,int k)
{
x=++tot;
key[x]=k;
siz[x]=1;
pre[x]=fa;
rev[x]=ch[x][1]=ch[x][0]=0;
}
void push_up(int x){
if(!x)return;
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
void upadte_rev(int x)
{
if(!x)return ;
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
void push_down(int x)
{
if(!x)return;
if(rev[x]){
upadte_rev(ch[x][0]);
upadte_rev(ch[x][1]);
rev[x]^=1;
}
}
void Rotate(int x,int kind)
{
int y=pre[x];
push_down(y);
push_down(x);
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
ch[x][kind]=y;
if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
pre[y]=x;
push_up(y);
push_up(x);
}
void Splay(int x,int goal)
{
while(pre[x]!=goal){
if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);
else{
int y=pre[x];
int kind=(ch[pre[y]][0]==y);
if(ch[y][kind]==x){
Rotate(x,!kind);
Rotate(x,kind);
}else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
if(goal==0)root=x;
}
void built(int &x,int L,int R,int fa)
{
if(L>R)return;
int mid=(R+L)>>1;
newnode(x,fa,mid);
built(ch[x][0],L,mid-1,x);
built(ch[x][1],mid+1,R,x);
push_up(x);
}
void init(int n)
{
siz[0]=pre[0]=0;
root=tot=ch[0][0]=ch[0][1]=0;
newnode(root,0,inf);
newnode(ch[root][1],root,inf);
built(ch[ch[root][1]][0],1,n,ch[root][1]);
push_up(ch[root][1]);
push_up(root);
}
int Get_kth(int x,int k){
push_down(x);
int sz=siz[ch[x][0]]+1;
if(sz==k)return x;
if(sz>k)return Get_kth(ch[x][0],k);
return Get_kth(ch[x][1],k-sz);
}
void reverse(int L,int R)
{
Splay(Get_kth(root,L-1),0);
Splay(Get_kth(root,R+1),root);
upadte_rev(ch[ch[root][1]][0]);
}
void append_to_end()
{
int t=ch[ch[root][1]][0];
ch[ch[root][1]][0]=0;
push_up(ch[root][1]);
push_up(root);
Splay(Get_kth(root,siz[root]-1),0);
Splay(Get_kth(root,siz[root]),root);
ch[ch[root][1]][0]=t;
pre[t]=ch[root][1];
push_up(ch[root][1]);
push_up(root);
}
void print(int x){
if(!x)return;
push_down(x);
print(ch[x][0]);
if(key[x]!=inf)printf("%d\n",key[x]);
print(ch[x][1]);
}
int main(int argc, char const *argv[])
{
int n,m,L,R;
while(~scanf("%d%d",&n,&m))
{
init(n);
while(m--){
scanf("%d%d",&L,&R);
reverse(L+1,R+1);
append_to_end();
}
print(root);
}
return 0;
}UVA 11922 Splay区间翻转+分裂+合并