http://acm.hdu.edu.cn/showproblem.php?pid=4351
线段树 每个节点保存前缀 后缀 和 剩余情况 中（k）(0<=k<=9) 是否出现
除了叶子节点外 其它节点要用左右孩子 来维护
求答案时类似
维护的过程中有重复的计算 需要用打表和位运算来优化 否则超时
注意0的情况
代码及其注释：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<stack>
#include<cmath>
#define LL long long
using namespace std;
const int N=100005;
struct node
{
int l,r,root;//root 为这一段总起来的 结果
int lt,rt,mt;//前缀 后缀 和其它情况 中k（0--9）是否出现 用二进制表示
}mem[N*4];
struct tt//同上
{
int lt,rt,mt,root;
}ans[N*4];
int mul[1024][1024];//将 i 和 j 两种情况合并
int a[N];
inline int Froot(int x)//只能处理小于等于18的情况
{
if(x>9)
return x-9;
return x;
}
void begin()//打表 来优化时间 否则超时
{
for(int x=1;x<1024;++x)
for(int y=1;y<1024;++y)
{
mul[x][y]=0;
for(int i=0;i<=9;++i)
{
if(x&(1<<i))
for(int j=0;j<=9;++j)
if(y&(1<<j))
mul[x][y]=(mul[x][y]|(1<<Froot(i+j)));
}
}
}
void updatemem(int x)//维护x 的前缀 后缀 等信息
{
mem[x].root=mul[ mem[ x<<1 ].root ][ mem[ x<<1|1 ].root ];//root 是左右子树 root 的 更新
mem[x].rt=(mem[ x<<1|1 ].rt | (mul[ mem[ x<<1 ].rt ][ mem[ x<<1|1 ].root]));//后缀由 右子树后缀 左子树后缀+右子树全部来更新
mem[x].lt=(mem[ x<<1 ].lt | (mul[ mem[ x<<1|1 ].lt ][ mem[ x<<1 ].root ]));//前缀由 左子树前缀 右子树前缀+左子树全部来更新
mem[x].mt=(mem[ x<<1 ].mt | mem[ x<<1|1 ].mt | (mul[ mem[ x<<1 ].rt ][ mem[ x<<1|1 ].lt ]));//其它 由 左子树其它 右子树其它 左子树后缀+右子树前缀更新
}
void updateans(int x)//同上
{
ans[x].root=mul[ ans[ x<<1 ].root ][ ans[ x<<1|1 ].root ];
ans[x].rt=(ans[ x<<1|1 ].rt | (mul[ ans[ x<<1 ].rt ][ ans[ x<<1|1 ].root]));
ans[x].lt=(ans[ x<<1 ].lt | (mul[ ans[ x<<1|1 ].lt ][ ans[ x<<1 ].root ]));
ans[x].mt=(ans[ x<<1 ].mt | ans[ x<<1|1 ].mt | (mul[ ans[ x<<1 ].rt ][ ans[ x<<1|1 ].lt ]));
}
void build(int x,int l,int r)//建树
{
mem[x].l=l;
mem[x].r=r;
if(l==r)
{
mem[x].lt=1<<a[l];//初始化
mem[x].rt=1<<a[l];
mem[x].mt=1<<a[l];
mem[x].root=1<<a[l];
return ;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
updatemem(x);//更新
}
void Fans(int x,int l,int r)
{
if(mem[x].l==l&&mem[x].r==r)
{
ans[x].lt=mem[x].lt;//答案搜索边界
ans[x].rt=mem[x].rt;
ans[x].mt=mem[x].mt;
ans[x].root=mem[x].root;
return ;
}
int mid=(mem[x].l+mem[x].r)>>1;
if(mid<l)
{
Fans(x<<1|1,l,r);//只在右子树 传结果上来
ans[x].lt=ans[x<<1|1].lt;
ans[x].rt=ans[x<<1|1].rt;
ans[x].mt=ans[x<<1|1].mt;
ans[x].root=ans[x<<1|1].root;
}else if(mid>=r)
{
Fans(x<<1,l,r);
ans[x].lt=ans[x<<1].lt;
ans[x].rt=ans[x<<1].rt;
ans[x].mt=ans[x<<1].mt;
ans[x].root=ans[x<<1].root;
}else
{
Fans(x<<1,l,mid);
Fans(x<<1|1,mid+1,r);
updateans(x);//左右都有 更新
}
}
int main()
{
//freopen("data.txt","r",stdin);
begin();
int T;
scanf("%d",&T);
for(int c=1;c<=T;++c)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
if(a[i]<=18)
a[i]=Froot(a[i]);
else//注意很大的情况
{
a[i]=a[i]%9;
if(a[i]==0)
a[i]=9;
}
}
build(1,1,n);
int q;
scanf("%d",&q);
printf("Case #%d:\n",c);
while(q--)
{
int l,r;
scanf("%d %d",&l,&r);
Fans(1,l,r);
int a=(ans[1].lt|ans[1].rt|ans[1].mt);
int k=0;
for(int i=9;k<5&&i>=0;--i)
{
if(a&(1<<i))
{
printf("%d",i);
++k;
if(k<5)
printf(" ");
}
}
while(k<5)
{
printf("-1");
++k;
if(k<5)
printf(" ");
}
printf("\n");
}
if(c<T)
printf("\n");
}
return 0;
}