區間合並的線段樹
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 100100
#define f(x) ((x)==0?0:((x)%9==0?9:(x)%9))
using namespace std;
struct Tree{
int l,r;
int ls,rs,all,num;
}tree[5*N];
int val[N],mul[1125][1125];
void init(){
int i,j,p,q;
for(i=0;i<=1023;i++)
for(j=i;j<=1023;j++){
mul[i][j]=0;
for(p=0;p<=9;p++)
if(i&(1<<p))
for(q=0;q<=9;q++)
if(j&(1<<q))
mul[i][j]|=(1<<f(p+q));
mul[j][i]=mul[i][j];
}
}
void build(int s,int t,int id){
tree[id].l=s,tree[id].r=t;
if(s==t){
tree[id].ls=tree[id].rs=tree[id].num=tree[id].all=1<<f(val[s]);
return ;
}
int mid=(s+t)>>1;
build(s,mid,id<<1);
build(mid+1,t,id<<1|1);
tree[id].all=tree[id<<1].all|tree[id<<1|1].all|mul[tree[id<<1].rs][tree[id<<1|1].ls]; //all表示所有情況
tree[id].num=mul[tree[id<<1].num][tree[id<<1|1].num]; //num表示此區間內所有數和的digital root
tree[id].ls=tree[id<<1].ls|mul[tree[id<<1].num][tree[id<<1|1].ls]; //ls表示所有含有區間左端點的區間的情況
tree[id].rs=tree[id<<1|1].rs|mul[tree[id<<1|1].num][tree[id<<1].rs];//rs表示所有含有區間右端點的區間的情況
}
struct Tree query(int s,int t,int id){
struct Tree t1,t2,t3;
if(tree[id].l==tree[id].r)return tree[id];
if(tree[id].l==s && tree[id].r==t)return tree[id];
int mid=(tree[id].l+tree[id].r)>>1;
if(mid>=t)return query(s,t,id<<1);
else if(mid<s)return query(s,t,id<<1|1);
else{
t1=query(s,mid,id<<1);
t2=query(mid+1,t,id<<1|1);
t3.all=t1.all|t2.all|mul[t1.rs][t2.ls];
t3.num=mul[t1.num][t2.num];
t3.ls=t1.ls|mul[t1.num][t2.ls];
t3.rs=t2.rs|mul[t2.num][t1.rs];
return t3;
}
}
int main(){
int t,T,n,q;
int i,j,l,r;
init();
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&val[i]);
build(1,n,1);
scanf("%d",&q);
printf("Case #%d:\n",t);
for(j=1;j<=q;j++){
scanf("%d %d",&l,&r);
struct Tree tem=query(l,r,1);
int num=1;
vector<int>vec;
vec.clear();
for(i=9;i>=0 && num<=5;i--){
if(tem.all&(1<<i)){
num++;
vec.push_back(i);
}
}
while(num<=5){
vec.push_back(-1);
num++;
}
for(i=0;i<vec.size();i++){
if(!i)printf("%d",vec[i]);
else printf(" %d",vec[i]);
}
puts("");
}
if(t!=T)puts("");
}
return 0;
}
