2015
05-23

# Digital root

The digital root (also repeated digital sum) of a number is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.
For example, the digital root of 65536 is 7, because 6+5+5+3+6=25 and 2+5=7.
The digital root of an interval is digital root of the sum of all numbers in that interval.

Consider a sequence A1,A2,A3……An, your task is to answer some queries[l,r]. For each query, tell the biggest five different digital roots among all continuous subintervals of interval[l,r]

In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 10) Then T cases follows. For each test case, the first line is an integer n indicating the length of sequence(1<=n<=100000); following one line containing n integer Ai(0<=Ai<=1000000000); the third line is an integer Q indicating the number of queries(1<=Q<=100000); following Q lines, each line indicating one query [l,r],(1<=l<=r<=n).

In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 10) Then T cases follows. For each test case, the first line is an integer n indicating the length of sequence(1<=n<=100000); following one line containing n integer Ai(0<=Ai<=1000000000); the third line is an integer Q indicating the number of queries(1<=Q<=100000); following Q lines, each line indicating one query [l,r],(1<=l<=r<=n).

1
5
101 240 331 4 52
3
1 3
4 5
1 5

Case #1:
8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4
Hint
For the first query, [1,3] has six subintervals: [1,1],[2,2],[3,3],[1,2],[2,3],[1,3]. Interval sums are 101,240,331,341,571,672, correspondence digital roots are 2,6,7
,8,4,6,the most biggest five are 8,7,6,4,2


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson l , mid , dex<<1
#define rson mid + 1 , r , dex<<1|1
#define havemid int mid = (l + r) >> 1

using namespace std;
const int Max = 100100;
int pass[10][1025];
//int root_l[Max];
//int root_r[Max];
//int root_a[Max];
//int root[Max<<2];

struct se
{
int root_l , root_r , root_a , root , dex;
se(int a = 0 , int b = 0 , int c = 0 , int d = 0 , int e = 0):root_l(a) , root_r(b) , root_a(c) , root(d) , dex(e) {}
bool check()
{
if(!root_l && !root_r && !root_a && !root)
return true;
else
return false;
}
} seg[Max<<2];

void out_root(int x)
{
for(int i = 0 ; i <= 9 ; i++)
if(x & (1 << i))
printf("%d " , i);
}

int Find_root(int x)
{
int tem = 0;
while(x)
{
tem += x%10;
x /= 10;
}
if(tem < 10)
return tem;
else
Find_root(tem);
}
inline int handle(int add , int root)
{
int tem = 0;
for(int i = 9 ; i >= 0 ; i--)
{
if(root & (1<<i))
tem |= (1 << Find_root(i + add));
}
return tem;
}
inline int handle2(int one , int second)
{
int tem = 0;
for(int i = 9 ; i >= 0 ; i--)
if(one & (1 << i))
tem |= pass[i][second];
return tem;
}
void init()
{
//    memset(pass , 0 , sizeof(pass));
//    for(int i = 0 ; i <= 9 ; i ++)
//        for(int j = 1 ; j <= 1024 ; j ++)
//            pass[i][j] = j | handle(i , j);

//    for(int i = 0 ; i <= 1024 ; i++)
//        for(int j = i ; j <= 1024 ; j++)
//            add[i][j] = add[j][i] = j | i | handle2(i , j);

memset(pass , 0 , sizeof(pass));
for(int i = 0 ; i <= 9 ; i ++)//pay attention! "i" is the root number  "j" is the value of the root number in binary system
for(int j = 1 ; j <= 1024 ; j ++)
pass[i][j] = handle(i , j);

//    for(int i = 1 ; i <= 9 ; i ++).
//    {
//        printf("pass[%d][%d]\n" , 1 , (1<<i|1));
//        out_root(pass[1][(1<<i|1)]);
//        printf("\n");
//    }

for(int i = 0 ; i <= 1024 ; i++)
for(int j = i ; j <= 1024 ; j++)
//
//    for(int i = 1 ; i <= 9 ; i ++)
//    {
//        printf("add[%d][%d]\n" , 2 , (1<<i|1));
//        printf("\n");
//    }
}

//void Push_up(int dex)
//{
//    seg[dex].root_l = seg[dex<<1].root_l | add[seg[dex<<1].root_a][seg[dex<<1|1].root_l];
//    seg[dex].root_r = seg[dex<<1|1].root_r | add[seg[dex<<1|1].root_a][seg[dex<<1].root_r];
//    seg[dex].root = seg[dex].root_l | seg[dex].root_r | add[seg[dex<<1].root_r][seg[dex<<1|1].root_l];
//
////    root_l[dex] = root_l[dex<<1] | add[root_a[dex<<1]][root_l[dex<<1|1]];
////    root_r[dex] = root_r[dex<<1|1] | add[root_a[dex<<1|1]][root_r[dex<<1]];
////    root[dex] = root_l[dex] | root_r[dex] | add[root_r[dex<<1]][root_l[dex<<1|1]];
//}
se Push_up(se lsn , se rsn)
{
se father;
if(lsn.check() && !rsn.check()) return father = rsn;
else if(!lsn.check() && rsn.check()) return father = lsn;
else if(lsn.check() && rsn.check())   return father;
father.root   = father.root_l | father.root_r | add[lsn.root_r][rsn.root_l] | lsn.root | rsn.root;
return father;
}

void build(int l , int r , int dex)
{
if(l == r)
{
int tem;
scanf("%d" , &tem);
seg[dex].root_a = seg[dex].root_l = seg[dex].root_r = seg[dex].root |= (1 << Find_root(tem));
//        root_a[dex] = root_l[dex] = root_r[dex] = root[dex] |= (1 << Find_root(tem));
return;
}
havemid;
build(lson);
build(rson);
seg[dex] = Push_up(seg[dex<<1] , seg[dex<<1|1]);
}

inline void m_out(int x)
{
int counter = 0;
int ans[5];
for(int i = 9 ; i >= 0 ; i--)
{
if(counter == 5)    break;
if(x & (1<<i))
ans[counter++] = i;
}
if(!counter)
printf("-1 -1 -1 -1 -1");
else
{
printf("%d" , ans[0]);
for(int i = 1 ; i < counter ; i++)
printf(" %d" , ans[i]);
for(int i = counter ; i < 5 ; i++)
printf(" -1");
}
printf("\n");
}

se query(int L , int R , int l , int r , int dex)
{
if(L <= l && R >= r)
return seg[dex];
havemid;
se tem_L , tem_R , tem_ans;
if(L <= mid)    tem_L = query(L , R , lson);
if(R >  mid)    tem_R = query(L , R , rson);
tem_ans = Push_up(tem_L , tem_R);
return tem_ans;
}

void out_build(int l , int r , int dex)
{
if(l == r)
{
printf("root[%d]:\n" , dex);
out_root(seg[dex].root);
printf("\n");
return;
}
havemid;
out_build(lson);
out_build(rson);
printf("root[%d]:\n" , dex);
out_root(seg[dex].root);
printf("\n");
}
int main()
{
//    freopen("DG.txt","r",stdin);
int t , cases = 1;
scanf("%d" , &t);
init();
while(t--)
{
printf("Case #%d:\n" , cases++);
memset(seg , 0 , sizeof(seg));
int n;
scanf("%d" , &n);
build(1 , n , 1);
//        out_build(1 , n , 1);
int m;
scanf("%d" , &m);
for(int i = 1 ; i <= m ; i++)
{
int a , b;
scanf("%d %d" , &a , &b);
//            cout<<"Bingo"<<endl;
se ans = query(a , b , 1 , n , 1);
m_out(ans.root);
}
if(t != 0)
printf("\n");
}
}