TJOI2013数字根

题面链接

洛谷

sol

我们先不考虑\(0\)，发现数字根\(=\)它\(mod 9\)。

我们前缀和一波，把区间和变成两数相减。

对于每个\(v\in\{0-8\}\)，（这里面的\(mod 9=0\)的相当于数字根为9），我们维护每个数\(a\)往后第一个可以和它组成\((b-a) mod 9=v\)的位置，称为\(OJBK\)位置。

那么对于一段区间，求出每个\(v\in\{0-8\}\)的最小\(OJBK\)位置，若它在区间里面，那么这段区间就可以组成这个\(v\)。

至于\(0\)我们特判一下区间内有没有\(0\)，然后忽略\(0\)。

总复杂度\(O(9nlogn+9q)\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

inline int in()

{

	int k=0;char ch=gt;

	while(ch<'-')ch=gt;

	while(ch>'-')k=k*10+ch-'0',ch=gt;

	return k;

}

const int N=1e5+5;

int c[N],a[N],st[10][N][20],las[10],lo[N],p[N];

inline int Get_mi(int x,int l,int r)

{

	l=std::max(l,0),r=std::max(r,0);

	if(l>r)return 0x3f3f3f3f;int k=lo[r-l+1];

	return std::min(st[x][l][k],st[x][r-(1<<k)+1][k]);

}

int main()

{

	int n=in(),tot=0;

	for(int i=1;i<=n;++i)

	{

		int t=in();p[i]=t;

		if(t){a[++tot]=t%9;continue;}

		++c[i];

	}

	for(int i=1;i<=n;++i)c[i]+=c[i-1];

	for(int i=1;i<=tot;++i)a[i]=(a[i]+a[i-1])%9;

	for(int i=2;i<=tot;++i)lo[i]=lo[i>>1]+1;

	for(int i=0;i<9;++i)

	{

		memset(las,0x3f,sizeof las);

		for(int j=tot;~j;--j)

		{

			int res=(a[j]+i)%9;

			st[i][j][0]=las[res];las[a[j]]=j;

		}

		for(int j=1;(1<<j)<=tot;++j)

			for(int k=0;k+(1<<j)<=tot;++k)

				st[i][k][j]=std::min(st[i][k][j-1],st[i][k+(1<<j-1)][j-1]);

	}

	int q=in();

	while(q--)

	{

		memset(las,-1,sizeof las);

		int L=in(),R=in(),cnt=0,l=L-c[L],r=R-c[R],fg=0;

		if(R-L!=r-l)fg=1;if(!p[L])++l;

		if(Get_mi(0,l-1,r-1)<=r)las[++cnt]=9;

		for(int i=8;i;--i)

			if(Get_mi(i,l-1,r-1)<=r)las[++cnt]=i;

		if(fg)las[++cnt]=0;

		for(int i=1;i<=5;++i)printf("%d ",las[i]);puts("");

	}

	return 0;

}