P3962 [TJOI2013]数字根

题意

数字根:这个数字每一位的数字加起来求和,反复这个过程直到和小于10。

给出序列\(a\)，询问区间\([l,r]\)连续的子区间里最大前5个不同的数字根，不够5个-1补全。

一个区间的数字根指区间和的数字根。

\(a_i\le 10^9,n\le 10^5\)

---

开始写了个线段树发现是个假做法给我气死了...

数字根结论：对自然数\(x\)，若\(x=0\)，数字根为\(0\)，否则为\((x-1)\bmod 9+1\)

做法：预处理每个位置右边最早可以出现根\(1,2,\dots 9\)的位置（\(0\)特判），扔到st表里面，然后询问直接查一下区间最小值是否不比右端点大就可以了。

---

Code:

#include <cstdio>

#include <algorithm>

#include <cctype>

using std::min;

const int N=1e5+10;

int read()

{

    int x=0;char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x;

}

int n,q,a[N],dew[N],f[N],yuy[N][10],Log[N];

struct yuu

{

    int st[N][20];

    void init()

    {

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

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

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

    }

    int query(int l,int r)

    {

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

        return min(st[l][d],st[r-(1<<d)+1][d]);

    }

}bee[10];

int main()

{

    n=read();

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

    {

        a[i]=read();

        dew[i]=dew[i-1]+(a[i]==0);

        f[i]=(f[i-1]+a[i])%9;

    }

    for(int i=0;i<9;i++) yuy[n+1][i]=n+1;

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

    {

        for(int j=0;j<9;j++) yuy[i][j]=yuy[i+1][j];

        if(a[i]) yuy[i][f[i]]=i;

    }

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

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

            bee[j].st[i][0]=yuy[i][(f[i-1]+j)%9];

    for(int i=2;i<=n;i++) Log[i]=Log[i>>1]+1;

    for(int i=0;i<9;i++) bee[i].init();

    q=read();

    for(int l,r,i=1;i<=q;i++)

    {

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

        int ct=5;

        for(int j=9;j&&ct;j--)

            if(bee[j==9?0:j].query(l,r)<=r)

                printf("%d ",j),--ct;

        if(ct&&dew[r]-dew[l-1]) printf("0 "),--ct;

        while(ct--) printf("-1 ");

        puts("");

    }

    return 0;

}

---

2019.2.12