题目描述
有 N 张牌和 N 堆牌。
牌和堆的编号都是 1,2,…,N。起初，第 i 堆只包含牌 i。
按顺序对每个 i=1,2,…,Q* 执行以下操作：
- 把牌 C**i 以及叠在它上面的所有牌（顺序不变）移动到牌 P**i 的上面。保证在执行操作前，牌 C**i 和牌 P**i 在不同的堆里，且牌 P**i 是某堆的最顶端。
操作全部完成后，求每堆牌的牌数。
约束条件
- 1≤N,Q≤3×105
- 1≤C**i,P**i≤N
- 操作按顺序执行时，每次操作前，牌 Ci* 和牌 *Pi* 必定在不同堆。
- 操作按顺序执行时，每次操作前，牌 P**i 必定是某堆的顶牌。
- 所有输入均为整数。
输入格式
标准输入格式如下：
N Q
C1 P1
C2 P2
⋮⋮
CQ PQ
输出格式
设 A**i 为最终第 ii 堆的牌数，按顺序输出 A1,A2,…,A**N*，用空格分隔。
样例 1
| Input复制 | Output复制 |
|---|---|
5 4 1 3 4 5 1 4 4 2 |
0 3 1 0 1 |
操作过程如图所示。
样例 2
| Input复制 | Output复制 |
|---|---|
7 8 3 1 5 4 2 5 5 7 2 3 6 2 3 4 5 1 |
2 0 0 4 0 0 1 |
算法分析
用双向链表解决，用pre和nxt两个数组分别存编号为i的牌的上面一个元素和下面一个元素，对于每次输入的C和P，断绝C和它下面的牌的连接，把C和P连接起来，就处理完毕了，输出时用一个f数组存储，遍历每张牌的上面和下面即可。
接下来展示一个TLE代码：
#include<bits/stdc++.h>
using namespace std;
int n,q;
int f[300005];
int pre[300005];//第i张牌的下面的编号
int nxt[300005];//第i张牌的上面的编号
int main(){cin>>n>>q;for(int i = 1; i<=n; i++){pre[i] = 0;nxt[i] = 0;}for(int i = 1; i<=q; i++){int x,y;cin>>x>>y;nxt[pre[x]] = 0;pre[x] = y;nxt[y] = x;}for(int i = 1; i<=n; i++){int cnt = -1;int t = i;while(t!=0){cnt++;t = nxt[t];}t = i;int last = t;while(t!=0){cnt++;last = t;t = pre[t];}f[last] = cnt;}for(int i = 1; i<=n; i++){cout<<f[i]<<" ";}return 0;
}
为什么会超时呢？因为此时的时间复杂度时O(NQ)的，有一些牌其实已经被同一堆的牌遍历过一遍了，再遍历就没有必要了。
解决方案：用vis数组标记该点是否已被访问，被访问就跳过。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,q;
int f[300005];
bool vis[300005];
int pre[300005];//第i张牌的下面的编号
int nxt[300005];//第i张牌的上面的编号
int main(){cin>>n>>q;for(int i = 1; i<=n; i++){pre[i] = 0;nxt[i] = 0;}for(int i = 1; i<=q; i++){int x,y;cin>>x>>y;nxt[pre[x]] = 0;pre[x] = y;nxt[y] = x;}for(int i = 1; i<=n; i++){if(vis[i]==1){continue;}int cnt = -1;int t = i;while(t!=0){cnt++;vis[t] = 1;t = nxt[t];}t = i;int last = t;while(t!=0){cnt++;vis[t] = 1;last = t;t = pre[t];}f[last] = cnt;}for(int i = 1; i<=n; i++){cout<<f[i]<<" ";}return 0;
}