5.7 省选模拟赛 超简单题 子序列自动机 树链剖分 倍增

LINK:超简单题

avatar
avatar

见微知著 这道题中扩展了一类问题的做法。

对于Q==1和|S|<=15

容易想到拿k在序列自动机上跑就行了。

这样复杂度每次是O(S)的。

考虑k<=1e6 容易想到有用的点只有1e6个暴力建出来然后查的时候O(1)查询 由于输出有限 所以记录一个pre倒着找答案即可.

code:值得一提的是 当方案数>1e18时可以强制=1e18.

const ll MAXN=300010,maxn=1000010;
ll T,n,Q,id;
char a[MAXN];
ll f[MAXN];
ll nex[MAXN][26],pre[maxn],pos[maxn],c[maxn];
inline ll dfs(ll x)
{
	if(f[x])return f[x];
	ll ans=1;
	rep(0,25,i)
	{
		ll tn=nex[x][i];
		if(tn!=n+1)ans=min(INF,ans+dfs(tn));
	}
	return f[x]=ans;
}
inline void dfs(ll x,ll las)
{
	if(id>=1000010)return;
	rep(0,25,i)
	{
		if(id>=1000010)return;
		ll tn=nex[x][i];
		if(tn!=n+1)
		{
			pos[++id]=i;
			pre[id]=las;
			dfs(tn,id);
		}
	}
}
inline void solve(ll x,ll y)
{
	ll cnt=0;
	while(x!=0&&y)
	{
		a[++cnt]=pos[x]+'a';
		x=pre[x];--y;
	}
	fep(cnt,1,i)printf("%c",a[i]);
	puts("");
}
inline void calc(ll x,ll y)
{
	ll cnt=0,now=0,cc;
	while(x)
	{
		rep(0,25,i)
		{
			ll tn=nex[now][i];
			if(tn!=n+1)
			{
				if(f[tn]>=x){now=tn;cc=i;break;}
				else x-=f[tn];
			}
		}
		--x;a[++cnt]=cc+'a';
	}
	int ww=max(1ll,cnt-y+1);
	rep(ww,cnt,i)printf("%c",a[i]);
	puts("");
}
signed main()
{
	//freopen("1.in","r",stdin);
	gc(a);gt(Q);
	n=strlen(a+1);
	rep(0,25,i)nex[n][i]=n+1;
	fep(n-1,0,i)
	{
		rep(0,25,j)nex[i][j]=nex[i+1][j];
		nex[i][a[i+1]-'a']=i+1;
	}
	dfs(0);--f[0];dfs(0,0);
	rep(1,Q,i)
	{
		ll p,k;
		get(k);get(p);
		if(f[0]<k){puts("-1");continue;}
		if(k<=1000000)solve(k,p);
		else calc(k,p);
	}
	return 0;
}

考虑100分。

可以发现 先不考虑输出 而是直接定位到字典序第k小的 是哪个节点。注意这里指的节点是 序列自动机本质上是一棵树 每个节点表示一个字符串 容易发现 节点个数=本质不同的子串个数.

定位这一步就很难解决了。不能暴力而且需要很快的定位。

这类似于SAM求本质不同的子串字典序第k小的 不过当时SAM对于多次询问也束手无策 这里可以直接上SA 这样采用二分就可以快速求出了。

不过序列自动机没有SA 考虑树链剖分.

先讨论总数量<=1e18时的时候.容易发现要找到节点到根节点需要爬logn条轻链。

但是此时是正着的过程 跳的时候可以二分重链上的位置 看一下是从什么时候离开了重链的。

发现二分再定位也很麻烦->倍增.

这样最多跳logn轻链也同时倍增logn次 复杂度就是log^2了。

考虑总数量>1e18时 之所以要特殊讨论是因为 这个地方不能瞎跳 也存在爆longlong的风险。

一种解决方法是 钦定第一个儿子的sz大于1e18时就是重儿子了 此时其他儿子显然也没用。

这样跳的时候复杂度不会出错 第一次离开重链的时候就和原来一样了。

值得注意的是 倍增的时候有一个致命的细节

for(int j=en[now];j>=0;j=min(j-1,en[now]))

由于钦定的根节点是0且倍增数组有些地方也是0 所以j在变得时候注意和en[now]取min.

至此可以拓展出在SAM上相似的问题时不需要转SA 而是直接进行树链剖分 和这道题相似的方法直接倍增做即可。

const ll MAXN=310010,maxn=1000010;
ll T,n,Q,id;
char a[MAXN];
ll nex[MAXN][26],son[MAXN],f[MAXN][20],en[MAXN];
ll sz[MAXN],g[MAXN][20];
signed main()
{
	freopen("1.in","r",stdin);
	gc(a);gt(Q);ll k;
	n=strlen(a+1);
	rep(0,25,i)nex[n][i]=n+1;
	fep(n-1,0,i)
	{
		rep(0,25,j)nex[i][j]=nex[i+1][j];
		nex[i][a[i+1]-'a']=i+1;
	}
	fep(n,0,i)
	{
		sz[i]=1;son[i]=n+1;
		rep(0,25,j)
		{
			sz[i]=min(sz[i]+sz[nex[i][j]],INF);	
			if(sz[nex[i][j]]>sz[son[i]])son[i]=nex[i][j];
		}
		f[i][0]=son[i];g[i][0]=1;
		rep(0,25,j)
		{
			if(nex[i][j]==son[i])break;
			g[i][0]=min(INF,g[i][0]+sz[nex[i][j]]);
		}
		rep(1,18,j)
		{
			f[i][j]=f[f[i][j-1]][j-1];
			if(!f[i][j])break;
			g[i][j]=min(INF,g[i][j-1]+g[f[i][j-1]][j-1]);
			en[i]=j;
		}
	}
	rep(1,Q,i)
	{
		get(k);ll get(p);++k;
		if(sz[0]<k){puts("-1");continue;}
		ll ww=k;ll now=0,len=0;
		//ww沿着重链跳
		while(ww)
		{
			for(ll j=en[now];j>=0;j=min(j-1,en[now]))
			{
				if(ww>g[now][j]&&ww<=g[now][j]+sz[f[now][j]])
				{
					ww-=g[now][j];len=len+(1<<j);
					now=f[now][j];
				}
			}
			--ww;		
			if(!ww)break;
			rep(0,25,i)
			if(ww<=sz[nex[now][i]])
				{
					now=nex[now][i];++len;
					break;
				}
			else ww-=sz[nex[now][i]];
		}
		p=min(p,len);len-=p;now=0;ww=k;
		while(len)
		{
			fep(en[now],0,j)
			{
				if((1<<j)<=len&&ww>g[now][j]&&ww<=g[now][j]+sz[f[now][j]])
				{
					ww-=g[now][j];len=len-(1<<j);
					now=f[now][j];
				}
			}
			if(!len)break;
			--ww;
			rep(0,25,i)
			if(ww<=sz[nex[now][i]])
				{
					now=nex[now][i];--len;
					break;
				}
			else ww-=sz[nex[now][i]];
		}
		//到达那个节点
		--ww;
		while(p)
		{
			rep(0,25,i)
			{
				if(ww<=sz[nex[now][i]])
				{
					--ww;--p;now=nex[now][i];
					putchar(i+'a');
					break;
				}
				else ww-=sz[nex[now][i]];
			}
		}
		puts("");
	}
	return 0;
}
原文地址:https://www.cnblogs.com/chdy/p/12850275.html