我先对数字根打了个表，然后得到了一个结论:(a)的数字根=((a-1)mod 9+1)
我在询问大佬后，大佬给出了一个简单的证明：
(ecause 10^nequiv 1(mod 9))
( herefore 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(iin[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();
}