Description

最近小M买了一个移动硬盘来储存自己电脑里不常用的文件。但是他把这些文件一股脑丢进移动硬盘后,觉得这些文件似乎没有被很好地归类,这样以后找起来岂不是会非常麻烦?
小M最终决定要把这些文件好好归类,把同一类地移动到一起。所以现在小M有了这几种操作:
1 u 表示把编号为u的文件放到最上面
2 u 表示把编号为u的文件放到最下面
3 u v 表示把编号为u的文件放到编号为v的文件的后面
已知在最开始的时候,1号文件到n号文件从上往下排布
现在小M已经给出了他所进行的所有操作,你能告诉他操作之后的序列是会变成什么样子吗?

Input

第一行为一个数字T(T<=10)表示数据组数
第二行为两个数字n、m(1<=n,m<=300000)表示序列长度和小M的操作次数
接下来m行每行两个或三个数字,具体含义见题面
保证数据合法

Output

输出一行表示小M操作结束后的序列

Sample Input

1
10 5
1 5
2 3
2 6
3 4 8
3 1 3

Sample Output

5 2 7 8 4 9 10 3 1 6

Hint

这道题之前见过好几次,没有一次写出来过,前几天认真研究了一下,终于写出来了。
思路:对每个位置,用l 和r两个数组记录该位置前面和后面的数的编号,每次变动的时候更新一下就好了。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAXN 300010
typedef long long ll;
int m, n;
int l[MAXN], r[MAXN];
void init()
{
r[0] = 1;
l[n + 1] = n;
for (int i = 1; i <= n; i++)
{
l[i] = i - 1;
r[i] = i + 1;
}
}
void con(int x, int y)
{
r[x] = y;
l[y] = x;
}
int main()
{
int T,x,u,v;
while (cin >> T)
{
while (T--)
{
cin >> n >> m;
init();
for (int i = 0; i < m; i++)
{
cin >> x;
if (x == 1)
{
cin >> u;
if (r[0] == u)
continue;
int l_u = l[u],r_u=r[u],r0=r[0];
con(l_u, r_u);
con(u, r0);
con(0, u);
}
else if (x == 2)
{
cin >> u;
if (l[n+1] == u)
continue;
int l_u = l[u], r_u = r[u], l_n = l[n+1];
con(l_u, r_u);
con(l_n, u);
con(u, n+1);
}
else
{
cin >> u >> v;
if (r[v] == u)
continue;
int l_u = l[u], r_u = r[u], r_v = r[v];
con(l_u, r_u);
con(u, r_v);
con(v, u);
}
}
int temp = r[0];
cout << temp;
while (r[temp] != (n + 1))
{
cout << " " << r[temp];
temp = r[temp];
}
cout << endl;
}
}
return 0;
}
/**********************************************************************
Problem: 1982
User: leo6033
Language: C++
Result: AC
Time:984 ms
Memory:4368 kb
**********************************************************************/

这题还能用链表来写,可以自己思考思考


05-11 15:53