CSU-1982 小M的移動硬盤

CSU-1982 小M的移動硬盤

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

---

題解

也是一道水題，但卻WA了很多發，這題用數組模擬雙向鏈表即可，先貼一開始WA的代碼

#include<bits/stdc++.h>
#define maxn 300050
using namespace std;
struct node {int l, r;
} a[maxn];
int main() {int t;scanf("%d", &t);while (t--) {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {a[i].l = i - 1;a[i].r = i + 1;}int head = 1, tail = n;for (int i = 1; i <= m; i++) {int q;scanf("%d", &q);if (q == 1) {int x;scanf("%d", &x);if (x == head) continue;if (x == tail) tail = a[x].l;a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[head].l = x;a[x].l = 0;a[x].r = head;head = x;}if (q == 2) {int x;scanf("%d", &x);if (x == tail) continue;if (x == head) head = a[x].r;a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[tail].r = x;a[x].l = tail;a[x].r = n + 1;tail = x;}if (q == 3) {int x, y;scanf("%d%d", &x, &y);if (x == y) continue;if (x == head) {head = a[x].r;}if (y == tail) {tail = x;}a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[x].r = a[y].r;a[a[y].r].l = x;a[x].l = y;a[y].r = x;}}int now = head;for (int i = 1; i < n; i++) {printf("%d ", now);now = a[now].r;}printf("%d\n", now);}return 0;
}
/**********************************************************************Problem: 1982User: ArtoriaxLanguage: C++Result: WA
**********************************************************************/

這個代碼只有一點沒注意到，即在q==3時，x處于tail時也會導致tail變化，很容易想的一個點，但卻WA了很多次，然后去網上搜題解，用a[0]表示鏈表頭，用a[n + 1]表示表尾才AC, 之后對拍一發才發現這個愚蠢的錯誤。

---

網上題解版：

#include<bits/stdc++.h>
#define maxn 300050
using namespace std;
struct node {int l, r;
} a[maxn];
int main() {int t;scanf("%d", &t);while (t--) {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {a[i].l = i - 1;a[i].r = i + 1;}a[0].r = 1;a[n + 1].l = n;for (int i = 1; i <= m; i++) {int q;scanf("%d", &q);if (q == 1) {int x;scanf("%d", &x);a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[x].l = 0;a[x].r = a[0].r;a[a[0].r].l = x;a[0].r = x;}if (q == 2) {int x;scanf("%d", &x);a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[x].r = n + 1;a[x].l = a[n + 1].l;a[a[n + 1].l].r = x;a[n + 1].l = x;}if (q == 3) {int x, y;scanf("%d%d", &x, &y);if (x == y) continue;a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[x].r = a[y].r;a[a[y].r].l = x;a[x].l = y;a[y].r = x;}}int now = a[0].r;for (int i = 1; i < n; i++) {printf("%d ", now);now = a[now].r;}printf("%d\n", now);}return 0;
}
/**********************************************************************Problem: 1982User: ArtoriaxLanguage: C++Result: ACTime:556 msMemory:4368 kb
**********************************************************************/

自己改正版:

#include<bits/stdc++.h>
#define maxn 300050
using namespace std;
struct node {int l, r;
} a[maxn];
int main() {int t;scanf("%d", &t);while (t--) {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {a[i].l = i - 1;a[i].r = i + 1;}int head = 1, tail = n;for (int i = 1; i <= m; i++) {int q;scanf("%d", &q);if (q == 1) {int x;scanf("%d", &x);if (x == head) continue;if (x == tail) tail = a[x].l;a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[head].l = x;a[x].l = 0;a[x].r = head;head = x;}if (q == 2) {int x;scanf("%d", &x);if (x == tail) continue;if (x == head) head = a[x].r;a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[tail].r = x;a[x].l = tail;a[x].r = n + 1;tail = x;}if (q == 3) {int x, y;scanf("%d%d", &x, &y);if (x == y) continue;if (a[y].r == x) continue;if (x == head) {head = a[x].r;}if (x == tail) {tail = a[x].l;}if (y == tail) {tail = x;}a[a[x].l].r = a[x].r;a[a[x].r].l = a[x].l;a[x].r = a[y].r;a[a[y].r].l = x;a[x].l = y;a[y].r = x;}}int now = head;for (int i = 1; i < n; i++) {printf("%d ", now);now = a[now].r;}printf("%d\n", now);}return 0;
}
/**********************************************************************Problem: 1982User: ArtoriaxLanguage: C++Result: ACTime:560 msMemory:4368 kb
**********************************************************************/