Description
给一个长度为 $n$ 的序列 $a_i$ 和一个数 $k$ 。现在把 $a$ 序列重复 $k$ 次生成一个数列 $b$ ，然后从第一位开始往一个栈中加入 $b_i$ 。如果这个栈里存在元素与 $b_i$ 相等那么一直 $\text{pop}$ 直到把那个数弹掉然后不加入新数；否则 $\text{push}$ $b_i$ 入栈。求全部操作完之后栈中的元素。
数据范围：$n \leq 2 \times 10^5, k \leq 10^{12}, a_i \leq 2 \times 10^5$
Solution
把 $a_i$ 排在一个圆周上，定义 $nxt_i = j$ 表示沿着顺时针方向第一个 $j$ 使得 $a_i=a_j$ 。
可以发现，假设目前栈中第一个元素是 $a_x = y$ ，那么下一次这个栈被整体清空是加入了
$nxt_x$ 之后。特别的，如果 $nxt_x = x$ ，那么就是再加一遍整个 $a_i$ 之后再次清空。
自然地可以想象 $x$ 向 $nxt_x +1$ 加一条边，表示 $x$ 之后下一个第一个下标会是 $nxt_x + 1$。这样的得到的图会形成一个一个环。也就是说，加了若干次 $a$ 后，全部都被清空，回到原点，也就是循环节。
我们可以把 $k$ 模上循环节，然后再对余下的不完整的部分直接模拟跳环的过程。如果一个时刻所加的数总数超出了 $k$ 就直接能够模拟一遍得到答案。
由于最后跳环每次最多会跳出去 $n+1$ 个点，并且循环节长度不会超过 $n(n+1)$ ，所以最后最多跳 $n$ 次以及统计答案时最多只需要考虑 $n$ 个点。所以时间复杂度为 $O(n)$
Code
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define fi first
#define se second
#define MP make_pair
#define pii pair <int, int>
#define pil pair <int, ll>
#define pli pair <ll, int>
#define pll pair <ll, ll>
#define All(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define ms0(x) memset(x, 0, sizeof(x))
#define ms1(x) memset(x, -1, sizeof(x))
#define oiu cerr << "Yes!" << endl;
#define O(x) cerr << #x << ": " << x << endl;
template <typename T> void printarr(T a[], int b, int e) {
if(b > e) return ;
for(int i = b; i < e; i++) cout << a[i] << " ";
cout << a[e] << " " << endl;
}
template <typename T> int chkmax(T &x, const T &y) {
return x < y ? x = y, 1 : 0;
}
template <typename T> int chkmin(T &x, const T &y) {
return x > y ? x = y, 1 : 0;
}
const int N = 5001000;
int n;
int nxt[N], fir[N], pos[N], a[N], ans[N], cnt, len[N];
ll k;
int main() {
scanf("%d %lld", &n, &k); k *= n;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if(!fir[a[i]]) {
fir[a[i]] = i;
pos[a[i]] = i;
}
else {
nxt[pos[a[i]]] = i;
pos[a[i]] = i;
}
nxt[i] = fir[a[i]];
}
for(int i = 1; i <= n; i++) {
if(nxt[i] > i) {
len[i] = nxt[i] - i + 1;
}
else len[i] = n - (i - nxt[i] - 1);
}
int u = 1; ll num = 0;
while(1) {
num += len[u];
u = nxt[u] + 1;
if(u > n) u -= n;
if(u == 1) break ;
}
k = k % num;
if(!k) return 0;
u = 1; num = 0;
while(1) {
num += len[u];
if(num >= k) {
num -= len[u];
for(int j = u; j <= u + k - num - 1; j++) {
int t = j; if(t > n) t -= n;
ans[++cnt] = a[t];
}
for(int i = 1; i <= cnt; i++)
pos[ans[i]] = fir[ans[i]] = nxt[i] = 0;
for(int i = 1; i <= cnt; i++) {
if(!fir[ans[i]]) {
fir[ans[i]] = i;
pos[ans[i]] = i;
}
else {
nxt[pos[ans[i]]] = i;
pos[ans[i]] = i;
}
nxt[i] = fir[ans[i]];
}
int p = 1;
while(p <= cnt) {
if(nxt[p] > p) {
p = nxt[p] + 1;
}
else {
printf("%d ", ans[p]);
p++;
}
}
return 0;
}
u = nxt[u] + 1;
if(u > n) u -= n;
}
return 0;
}
|