Do Not Duplicate
题目链接：https://atcoder.jp/contests/agc036/tasks/agc036_b
题解：
首先最后肯定至多只有$n$个数。
我们想处理出来每个点下一个一样的数的下一个数。
有点绕口....
处理出来了之后，暴力找环然后暴力跳就好。
代码：
#include <bits/stdc++.h>#define N 200010 using namespace std;typedef long long ll;int a[N], pre[N], nxt[N], val[N];char *p1, *p2, buf[100000];#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )int rd() {int x = 0;char c = nc();while (c < 48) {c = nc();}while (c > 47) {x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();}return x;
}ll rd2() {ll x = 0;char c = nc();while (c < 48) {c = nc();}while (c > 47) {x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();}return x;
}int First[N];int main() {int n = rd();ll k = rd2();for (int i = 1; i <= n; i ++ ) {a[i] = rd();}if (n == 1) {if (k & 1) {printf("%d\n", a[1]);}return 0;}for (int i = n; i; i -- ) {First[a[i]] = i;}for (int i = 1; i <= n; i ++ ) {if (pre[a[i]]) {nxt[pre[a[i]]] = (i + 1) % n;if (!nxt[pre[a[i]]]) {nxt[pre[a[i]]] = n;}}pre[a[i]] = i;}for (int i = 1; i <= n; i ++ ) {if (!nxt[i]) {if (First[a[i]] != i) {nxt[i] = First[a[i]] + 1;}else {if (i == n) {nxt[i] = 1;}else {nxt[i] = i + 1;}}}}for (int i = 1; i <= n; i ++ ) {if (nxt[i] >= i + 2) {val[i] = nxt[i] - i;}else {val[i] = nxt[i] + n - i;}}if (nxt[n] == 1) {val[n] = n + 1;}ll mdl = 0;int now = 1;while (1) {mdl += val[now];now = nxt[now];if (now == 1) {break;}}ll pre = mdl / n;// cout << pre << endl ;k %= pre;if (!k) {return 0;}// puts("Fuck");int id = 1;now = 1;while (1) {if (nxt[now] >= now + 2) {now = nxt[now];continue;}if (id == k) {if (nxt[now] == 1 && now != n) {return 0;}printf("%d ", a[now]);if (now == n) {return 0;}now ++ ;}else {id ++ ;now = nxt[now];}}return 0;
}
小结：想题的时候，多想一些特殊情况。比如边界值啊，极值啊这种。