[HDU-3487]Play with Chain

F - Play with Chain

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u

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

						<div style="font-family:'Courier New',Courier,monospace;">
							8 2
CUT 3 5 4
FLIP 2 6
-1 -1
						</div>

8 2

CUT 3 5 4

FLIP 2 6

-1 -1

</div>

Sample Output

						<div style="font-family:'Courier New',Courier,monospace;">
							1 4 3 7 6 2 5 8
						</div>

1 4 3 7 6 2 5 8

</div>

题意很简单，就是splay的区间操作。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=3e5+10;

int sze[maxn],rev[maxn],key[maxn],pre[maxn],ch[maxn][2];
int ans[maxn];
int root,tot;

inline void newnode(int &x,int fa,int k)
{
    x=++tot;
    sze[x]=1;
    rev[x]=ch[x][0]=ch[x][1]=0;
    pre[x]=fa;
    key[x]=k;
}

inline void Modify(int x)
{
    if (!x) return;
    rev[x]^=1;
}

inline void push_down(int x)
{
    if (x&&rev[x])
    {
        swap(ch[x][0],ch[x][1]);
        Modify(ch[x][0]);
        Modify(ch[x][1]);
        Modify(x);
    }
}

inline void push_up(int x)
{
    if (!x) return;
    sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+1;
    return;
}

void build(int &x,int L,int R,int fa)
{
    if (L>R) return ;
    int M=(L+R)>>1;
    newnode(x,fa,M);
    build(ch[x][0],L,M-1,x);
    build(ch[x][1],M+1,R,x);
    push_up(x);
}

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);
}


//spaly x to the child of goal,if goal=0, splay x to the root;
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;
}

int Get_kth(int x,int k)
{
    push_down(x);
    int tz=sze[ch[x][0]]+1;
    if (tz==k) return x;
    if (tz>k) return Get_kth(ch[x][0],k);
    return Get_kth(ch[x][1],k-tz);
}

void init(int n)
{
    root=tot=sze[0]=rev[0]=pre[0]=ch[0][0]=ch[0][1]=0;
    newnode(root,0,-1);
    newnode(ch[root][1],root,n+1);
    build(ch[ch[root][1]][0],1,n,ch[root][1]);
    push_up(ch[root][1]);
    push_up(root);
}

int Get_max(int x)
{
    push_down(x);
    while(ch[x][1])
    {
        x=ch[x][1];
        push_down(x);
    }
    return x;
}

void Merge(int root1,int root2)
{
    ch[root1][1]=root2;
    pre[root2]=root1;
}

int __;
void travel(int x)
{
    if (!x) return;
    push_down(x);
    travel(ch[x][0]);
    ans[__++]=key[x];
    travel(ch[x][1]);

}


int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if (n<0&&m<0) return 0;
        init(n);
        char op[10];
        int L,R,C;
        while(m--)
        {
            scanf("%s%d%d",op,&L,&R);
            if (op[0]=='F')
            {
                Splay(Get_kth(root,L),0);
                Splay(Get_kth(root,R+2),root);
                Modify(ch[ch[root][1]][0]);
            }
            else {
                scanf("%d",&C);
                Splay(Get_kth(root,L),0);
                Splay(Get_kth(root,R+2),root);
                int root1=ch[ch[root][1]][0];
                ch[ch[root][1]][0]=0;
                push_up(ch[root][1]);
                push_up(root);
                Splay(Get_kth(root,C+1),0);
                int root2=ch[root][1];
                Merge(root,root1);
                push_up(root);
                Splay(Get_max(root),0);
                Merge(root,root2);
                push_up(root);

            }
        }
        __=0;
        travel(root);
        for (int i=1;i<=n;i++)
        {
            printf("%d%c",ans[i],i==n?'\n':' ');
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=3e5+10;

int sze[maxn],rev[maxn],key[maxn],pre[maxn],ch[maxn][2];

int ans[maxn];

int root,tot;

inline void newnode(int &x,int fa,int k)

{

x=++tot;

sze[x]=1;

rev[x]=ch[x][0]=ch[x][1]=0;

pre[x]=fa;

key[x]=k;

}

inline void Modify(int x)

{

if (!x) return;

rev[x]^=1;

}

inline void push_down(int x)

{

if (x&&rev[x])

{

swap(ch[x][0],ch[x][1]);

Modify(ch[x][0]);

Modify(ch[x][1]);

Modify(x);

}

inline void push_up(int x)

{

if (!x) return;

sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+1;

return;

}

void build(int &x,int L,int R,int fa)

{

if (L>R) return ;

int M=(L+R)>>1;

newnode(x,fa,M);

build(ch[x][0],L,M-1,x);

build(ch[x][1],M+1,R,x);

push_up(x);

}

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);

}

//spaly x to the child of goal,if goal=0, splay x to the root;

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;

}

int Get_kth(int x,int k)

{

push_down(x);

int tz=sze[ch[x][0]]+1;

if (tz==k) return x;

if (tz>k) return Get_kth(ch[x][0],k);

return Get_kth(ch[x][1],k-tz);

}

void init(int n)

{

root=tot=sze[0]=rev[0]=pre[0]=ch[0][0]=ch[0][1]=0;

newnode(root,0,-1);

newnode(ch[root][1],root,n+1);

build(ch[ch[root][1]][0],1,n,ch[root][1]);

push_up(ch[root][1]);

push_up(root);

}

int Get_max(int x)

{

push_down(x);

while(ch[x][1])

{

x=ch[x][1];

push_down(x);

}

return x;

}

void Merge(int root1,int root2)

{

ch[root1][1]=root2;

pre[root2]=root1;

}

int __;

void travel(int x)

{

if (!x) return;

push_down(x);

travel(ch[x][0]);

ans[__++]=key[x];

travel(ch[x][1]);

}

int main()

{

int n,m;

while(scanf("%d%d",&n,&m)!=EOF)

{

if (n<0&&m<0) return 0;

init(n);

char op[10];

int L,R,C;

while(m--)

{

scanf("%s%d%d",op,&L,&R);

if (op[0]=='F')

{

Splay(Get_kth(root,L),0);

Splay(Get_kth(root,R+2),root);

Modify(ch[ch[root][1]][0]);

}

else {

scanf("%d",&C);

Splay(Get_kth(root,L),0);

Splay(Get_kth(root,R+2),root);

int root1=ch[ch[root][1]][0];

ch[ch[root][1]][0]=0;

push_up(ch[root][1]);

push_up(root);

Splay(Get_kth(root,C+1),0);

int root2=ch[root][1];

Merge(root,root1);

push_up(root);

Splay(Get_max(root),0);

Merge(root,root2);

push_up(root);

}

__=0;

travel(root);

for (int i=1;i<=n;i++)

{

printf("%d%c",ans[i],i==n?'\n':' ');

}

return 0;

}

槿叶轩

优秀是一种习惯

[HDU-3487]Play with Chain

About the Author: zhuyeye

发表回复取消回复

2023年 9月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

You May Also Like

[模板]圆与多边形交的面积

[模板]旋转卡壳

About the Author: zhuyeye

发表回复 取消回复

发表回复取消回复