HDU 4351 Digital root 线段树区间合并

依然不是十分理解……待考虑……
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 #define lson l, m, rt << 1
  7 #define rson m + 1, r, rt << 1 | 1
  8 
  9 using namespace std;
 10 
 11 const int MAXN = 122222;
 12 
 13 struct node
 14 {
 15     int num;
 16     int lnode, rnode;
 17     int root;
 18     node(): num(0), lnode(0), rnode(0), root(0){ }
 19 };
 20 
 21 int root[ MAXN << 2 ];
 22 int num[ MAXN << 2 ];
 23 int lnode[ MAXN << 2 ];
 24 int rnode[ MAXN << 2 ];
 25 int all[ 1 << 11 ][ 1 << 11 ];
 26 
 27 int GetRoot( int a )
 28 {
 29     if ( !a ) return 0;
 30     if ( a % 9 ) return a % 9;
 31     return 9;
 32 }
 33 
 34 void init()
 35 {
 36     for ( int i = 0; i < ( 1 << 10 ); ++i )
 37         for ( int j = 0; j < ( 1 << 10 ); ++j )
 38         {
 39             all[i][j] = 0;
 40             for ( int x = 0; x < 10; ++x )
 41                 if ( i & ( 1 << x ) )
 42                 {
 43                     for ( int y = 0; y < 10; ++y )
 44                         if ( j & ( 1 << y ) )
 45                             all[i][j] |= ( 1 << GetRoot( x + y ) );
 46                 }
 47         }
 48     return;
 49 }
 50 
 51 void PushUp( int rt )
 52 {
 53     int lc = rt << 1;
 54     int rc = rt << 1 | 1;
 55     root[rt] = root[lc] | root[rc] | all[ rnode[lc] ][ lnode[rc] ];
 56     num[rt] = all[ num[lc] ][ num[rc] ];
 57     lnode[rt] = lnode[lc] | all[ num[lc] ][ lnode[rc] ];
 58     rnode[rt] = rnode[rc] | all[ num[rc] ][ rnode[lc] ];
 59     return;
 60 }
 61 
 62 void build( int l, int r, int rt )
 63 {
 64     if ( l == r )
 65     {
 66         int a;
 67         scanf( "%d", &a );
 68         a = GetRoot(a);
 69         lnode[rt] = rnode[rt] = num[rt] = root[rt] = ( 1 << a );
 70         return;
 71     }
 72 
 73     int m = ( l + r ) >> 1;
 74     build( lson );
 75     build( rson );
 76     PushUp( rt );
 77     return;
 78 }
 79 
 80 node Query( int L, int R, int l, int r, int rt )
 81 {
 82     if ( L <= l && r <= R )
 83     {
 84         node D;
 85         D.root = root[rt];
 86         D.lnode = lnode[rt];
 87         D.rnode = rnode[rt];
 88         D.num = num[rt];
 89         return D;
 90     }
 91 
 92     int m = ( l + r ) >> 1;
 93 
 94     if ( R <= m ) return Query( L, R, lson );
 95     else if ( L > m ) return Query( L, R, rson );
 96     else
 97     {
 98         node LD, RD, D;
 99         LD = Query( L, R, lson );
100         RD = Query( L, R, rson );
101         D.root = LD.root | RD.root | all[ LD.rnode ][ RD.lnode ];
102         D.num = all[ LD.num ][ RD.num ];
103         D.lnode = LD.lnode | all[ LD.num ][ RD.lnode ];
104         D.rnode = RD.rnode | all[ RD.num ][ LD.rnode ];
105         return D;
106     }
107 }
108 
109 int main()
110 {
111     init();
112     int T, cas = 0;
113     scanf( "%d", &T );
114     while ( T-- )
115     {
116         int n;
117         scanf( "%d", &n );
118         build( 1, n, 1 );
119 
120         int Q;
121         scanf( "%d", &Q );
122         printf( "Case #%d:
", ++cas );
123         while ( Q-- )
124         {
125             int a, b;
126             scanf( "%d%d", &a, &b );
127             node ans = Query( a, b, 1, n, 1 );
128 
129             int cnt = 0;
130             bool first = false;
131             for ( int i = 9; i >= 0 && cnt < 5; --i )
132                 if ( ans.root & ( 1 << i ) )
133                 {
134                     if ( first ) putchar(' ');
135                     printf( "%d", i );
136                     first = true;
137                     ++cnt;
138                 }
139             for ( ; cnt < 5; ++cnt ) printf(" -1");
140             puts("");
141         }
142 
143         if ( T ) puts("");
144     }
145     return 0;
146 }