【AtCoder Grand 036B】Do Not Duplicate 题解

题目大意

  有一个长度为 $n$ 的数组 $a_0,\cdots,a_{n-1}$，把它拼 $k$ 次，得到 $a_0,\cdots,a_{nk-1}$。
  有一个初始为空的数组 $X$，对于 $0 \leq i < nk$，依次进行下面的操作：

• 若 $X$ 不含 $a_i$，则把 $a_i$ 加到 $X$ 的末尾；
• 若 $X$ 含有 $a_i$，则一直删除 $X$ 的末尾直至 $X$ 不含 $a_i$。

  求最终的 $X$ 数组。

  $n,a_i \leq 2\times10^5,\ \ k \leq 10^{12}$

题解

  把 $a_{ik},\cdots,a_{ik+n-1}$ 叫做第 $i$ 层。

  假设 $a_0,\cdots,a_{n-1}$ 是个循环数组，每个 $a_i$ 找到它下一个跟他相同的元素，假设是 $a_j$，那么 $i$ 向 $(j+1)\mod n$ 连边，边权为这条边跨过了几层。比如：

  由于每个点都有一条出边，那么这回是一棵环套树，也即有循环节。

  $O(n)$ 找到循环节，然后通过循环节快速走到最后一层，再暴力最后一层。

  题解没有找循环节，而是用倍增来求每个点走 $2^k$ 层之后到哪。萌新第一次艹标算好紧张啊。。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

struct D{
	int i;
	LL k;
};

const int maxn=2e5+5;

int n,a[maxn],occur[maxn],d0;
LL k;
D p[maxn],d[maxn];
bool bz[maxn];

int ans0,ans[maxn];
void Last(int x)
{
	memset(bz,0,sizeof(bz));
	fo(i,x,n) if (!bz[a[i]])
	{
		ans[++ans0]=a[i];
		bz[a[i]]=1;
	} else
	{
		while (bz[a[i]]) bz[ans[ans0--]]=0;
	}
	fo(i,1,ans0) printf("%d ",ans[i]);
}

int main()
{
	scanf("%d %lld",&n,&k);
	fo(i,1,n) scanf("%d",&a[i]);
	
	fd(i,n,1)
	{
		if (occur[a[i]])
		{
			if (occur[a[i]]==n) p[i]=(D){1,1ll}; else p[i]=(D){occur[a[i]]+1,0ll};
		}
		occur[a[i]]=i;
	}
	memset(occur,0,sizeof(occur));
	fo(i,1,n)
	{
		if (!occur[a[i]]) occur[a[i]]=i;
		if (!p[i].i)
		{
			if (occur[a[i]]==n) p[i]=(D){1,2ll}; else p[i]=(D){occur[a[i]]+1,1ll};
		}
	}
	
	D i=(D){1,1};
	memset(occur,0,sizeof(occur));
	for(; i.k<k; i.k+=p[i.i].k, i.i=p[i.i].i)
	{
		d[++d0]=i;
		if (occur[i.i]) break; else occur[i.i]=d0;
	}
	
	if (i.k==k) {Last(i.i); return 0;}
	LL cir=d[d0].k-d[occur[d[d0].i]].k;
	i.k=d[occur[d[d0].i]].k+(k-d[occur[d[d0].i]].k)/cir*cir;
	
	for(; i.k<k; i.k+=p[i.i].k, i.i=p[i.i].i);
	Last(i.i);
}