HDU 4351 Digital root 线段树 区间合并

看了解题报告后说有一种离线不用线段树的做法，表示不解

只会用线段树做

因为题目中所查询的区间，是所有的子区间的结果的并。所以区间合并就很必要了。

每个结点，记录这个区间的和的数根， 记录本区间内从左端点为端点往右的连续区间出现的数根，从右端点为端点往左的连续区间出现的数根，以及整个区间能出现的数根

比赛的时候狂WA一下午。

最后发现查询的时候左右区间合并有问题，查询的时候也需要像pushUp操作那样将左右查询的区间进行合并，注意要使用三段查询，两段的话我不知道怎么处理。

改完之后各种TLE。 然后发现它卡了常数。把可以合并的循环全都合并了

然后还TLE，加上输入输出优化后卡时限过了。

最后发现是求数根的函数调用太多的缘故，加个inline 貌似就快了500ms。

或者干脆不用函数，每回都直接求好了。 一个数的数根就是，如果是9的倍数，数根是9，否则就是模9， 两个数的和的数根就是数根的和的数根

这样一弄又快500ms，

最后用G++交的， 1000ms左右

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 100005
#define MAXM 320005
#define INF 100000007
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
int n;
int a[MAXN];
bool ls[4 * MAXN][10], rs[4 * MAXN][10], ok[4 * MAXN][10];
int sum[4 * MAXN];
struct node
{
    bool ls[10], rs[10], ok[10];
    int sum;
    void init()
    {
        memset(ls, 0, sizeof(ls));
        memset(rs, 0, sizeof(rs));
        memset(ok, 0, sizeof(ok));
    }
};
void up(int rt)
{
    ok[rt][sum[lch(rt)]] = 1;
    ok[rt][sum[rch(rt)]] = 1;
    for(int i = 0; i < 10; i++)
    {
        if(ls[lch(rt)][i]) ls[rt][i] = 1;
        if(rs[rch(rt)][i]) rs[rt][i] = 1;
        if(ok[lch(rt)][i] || ok[rch(rt)][i]) ok[rt][i] = 1;
        if(ls[rch(rt)][i])
        {
            int v = sum[lch(rt)] + i;
            if(v > 9) v -= 9;
            ls[rt][v] = 1;
            ok[rt][v] = 1;
        }
        if(rs[lch(rt)][i])
        {
            int v = sum[rch(rt)] + i;
            if(v > 9) v -= 9;
            rs[rt][v] = 1;
            ok[rt][v] = 1;
            for(int j = 0; j < 10; j++)
                if(ls[rch(rt)][j])
                {
                    v = i + j;
                    if(v > 9) v -= 9;
                    ok[rt][v] = 1;
                }
        }
    }
    sum[rt] = sum[lch(rt)] + sum[rch(rt)];
    if(sum[rt] > 9) sum[rt] -= 9;
    ok[rt][sum[rt]] = 1;
}
void build(int l, int r, int rt)
{
    memset(rs[rt], 0, sizeof(rs[rt]));
    memset(ls[rt], 0, sizeof(ls[rt]));
    memset(ok[rt], 0, sizeof(ok[rt]));
    if(l == r)
    {
        rs[rt][a[l]] = 1;
        ls[rt][a[l]] = 1;
        ok[rt][a[l]] = 1;
        sum[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    up(rt);
}
int out[11];
void query(int L, int R, int l, int r, int rt, node &p)
{
    if(L <= l && R >= r)
    {
        p.sum = sum[rt];
        p.ok[sum[rt]] = 1;
        for(int i = 0; i < 10; i++)
        {
            if(ok[rt][i]) p.ok[i] = 1;
            if(ls[rt][i]) p.ls[i] = 1;
            if(rs[rt][i]) p.rs[i] = 1;
        }
        return;
    }
    int m = (l + r) >> 1;
    if(m < L) query(L, R, rson, p);
    else if(m >= R) query(L, R, lson, p);
    else
    {
        node lf, rf;
        lf.init(), rf.init();
        query(L, m, lson, lf);
        query(m + 1, R, rson, rf);
        p.sum = lf.sum + rf.sum;
        if(p.sum > 9) p.sum -= 9;
        p.ok[p.sum] = 1;
        for(int i = 0; i < 10; i++)
        {
            if(lf.ls[i]) p.ls[i] = 1;
            if(rf.rs[i]) p.rs[i] = 1;
            if(lf.ok[i] || rf.ok[i]) p.ok[i] = 1;
            if(rf.ls[i])
            {
                int v = i + lf.sum;
                if(v > 9) v -= 9;
                p.ls[v] = 1;
                p.ok[v] = 1;
            }
            if(lf.rs[i])
            {
                int v = i + rf.sum;
                if(v > 9) v -= 9;
                p.rs[v] = 1;
                p.ok[v] = 1;
                for(int j = 0; j < 10; j++)
                    if(rf.ls[j])
                    {
                        int v = i + j;
                        if(v > 9) v -= 9;
                        p.ok[v] = 1;
                    }
            }
        }
    }
}
int in()
{
    int flag = 1;
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' || ch == '\n');
    if(ch == '-') flag = -1;
    else
        a += ch - '0';
    while((ch = getchar()) != ' ' && ch != '\n')
    {
        a *= 10;
        a += ch - '0';
    }
    return flag * a;
}
void Out(int a)
{
    if(a < 0)
    {
        putchar('-');
        a = -a;
    }
    if(a >= 10)Out(a / 10);
    putchar(a % 10 + '0');
}
int main()
{
    int T, cas = 0;
    T = in();
    //scanf("%d", &T);
    while(T--)
    {
        if(cas) printf("\n");
        n = in();
        //scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            //scanf("%d", &a[i]);
            a[i] = in();
            if(a[i] && a[i] % 9 == 0) a[i] = 9;
            else a[i] = a[i] % 9;
        }
        build(1, n, 1);
        int ask, x, y;
        printf("Case #%d:\n", ++cas);
        scanf("%d", &ask);
        int tp[10], fk[10];
        while(ask--)
        {
            //scanf("%d%d", &x, &y);
            x = in();
            y = in();
            node ans;
            ans.init();
            query(x, y, 1, n, 1, ans);
            int ct = 0;
            for(int i = 9; i >= 0; i--)
                if(ans.ok[i])
                {
                    tp[ct++] = i;
                    if(ct >= 5) break;
                }
            for(int i = 0; i < ct; i++)
            {
                //printf("%d", tp[i]);
                Out(tp[i]);
                if(i == ct - 1 && ct == 5) putchar('\n');
                else putchar(' ');
            }
            if(ct < 5)
            {
                for(int i = 0; i < 5 - ct; i++)
                {
                    Out(-1);
                    //printf("-1");
                    if(i == 4 - ct) putchar('\n');
                    else putchar(' ');
                }
            }
        }
    }
    return 0;
}