题面

我先对数字根打了个表，然后得到了一个结论:\(a\)的数字根=\((a-1)mod 9+1\)

我在询问大佬后，大佬给出了一个简单的证明：

\(\because 10^n\equiv 1(mod 9)\)

\(\therefore a_{n}*10^n+a_{n-1}*10^{n-1}+...+a_{1}\equiv a_{n}+a_{n-1}+...+a_{1}(mod 9)\)

这样的话一个区间\([l,r]\)的数字根就可以转化为\((pre_{r}-pre_{l-1}-1)mod 9+1\)，\(pre_{i}\)表示前缀和。

考虑预处理出一个数组\(last_{i,j}\)表示右端点为\(i\)数字根为\(j\)的区间的左端点的\(max\)。

但是这样的话按原式子做感觉很麻烦。

所以再把这个式子拆一下得:\((pre_{r}-pre_{l-1}-1)mod 9+1=((pre_{r}-1)mod 9-pre_{l-1}mod 9+9)mod 9+1\)

这样就好搞多了。

那处理出来这个\(last\)有什么用呢...

考虑如果查询一个区间内是否存在一个子区间的数字根为\(j\)的话，我们只要查询\(max(last_{i,j})<=l(i\in[l,r])\)就行了。

那么只要求个区间max是否\(<=l\)就行了，\(st\)，线段树随便上吧。

网上另外两篇题解都是暴力是smg，\(10^5\)个\(0\)随便卡啊

#include<bits/stdc++.h>

#define For(i,x,y) for (register int i=(x);i<=(y);i++)

#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)

#define cross(i,u) for (register int i=first[u];i;i=last[i])

using namespace std;

typedef long long ll;

inline ll read(){

    ll x=0;int ch=getchar(),f=1;

    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();

    if (ch=='-'){f=-1;ch=getchar();}

    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

const int N = 1e5+10;

int n,a[N];

ll pre[N];

inline void rd(){

	n=read();

	For(i,1,n) a[i]=read(),pre[i]=pre[i-1]+a[i];

}

int Log[N],last[N][10],now[10],p[20],Max[N][20][10];

inline void init(){

	For(i,1,8) now[i]=-1;

	For(i,1,n){

		if (!a[i]){For(j,1,9) last[i][j]=last[i-1][j];last[i][0]=i-1;}

			else{For(j,0,8) last[i][((pre[i]-1)%9-j+9)%9+1]=now[j];last[i][0]=-1;}

		now[pre[i]%9]=i;

		//For(j,1,9) printf("%d ",last[i][j]);puts("");

	}

	For(i,1,n) Log[i]=log2(i);

	p[0]=1;

	For(i,1,Log[n]) p[i]=p[i-1]<<1;

	For(i,1,n)

		For(j,0,9) Max[i][0][j]=last[i][j];

	For(j,1,Log[n])

		For(i,1,n-p[j]+1)

			For(k,0,9) Max[i][j][k]=max(Max[i][j-1][k],Max[i+p[j-1]][j-1][k]);

}

inline int query(int l,int r,int k){

	int L=Log[r-l+1];

	return max(Max[l][L][k],Max[r-p[L]+1][L][k]);

}

int q,l,r,cnt;

inline void work(){

	q=read();

	while (q--){

		l=read(),r=read(),cnt=0;

		Dow(i,9,0)

			if (query(l,r,i)+1>=l){

				printf("%d ",i),cnt++;

				if (cnt==5) break;

			}

		For(i,cnt+1,5) printf("-1 ");puts("");

	}

}

int main(){

	rd(),init(),work();

}