hdu 4315 Digital root 【多校6】【线段树】

线段树，居然pe了一次。。现场赛pe可是算wa的。。这尼玛！

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
/************ for topcoder by zz1215 *******************/
#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FFF(i,a)        for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define MAX(a,b)        ((a)>(b)?(a):(b))
#define MIN(a,b)        ((a)<(b)?(a):(b))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-9;
const double pi = acos(-1.0);
const int maxn = 100011;
const int maxz = 1<<10;

struct zz
{
	int l;
	int r;
	int x;
	int y;
	int h;
	int t;
}zx[maxn<<2+1];

int n,c;
int a[maxn];
int f[maxz+1][maxz+1];
int s[10][maxz];

int get(int x)
{	
	if(!x) return 0;
	x%=9;
	if(!x) return 9;	
	return x;
}

void up(int root)
{
	zx[root].t = get(zx[root<<1].t+zx[root<<1|1].t);
	zx[root].h = zx[root<<1].h | zx[root<<1|1].h;
	zx[root].h |= f[zx[root<<1].y][zx[root<<1|1].x];
	zx[root].x = zx[root<<1].x | s[zx[root<<1].t][zx[root<<1|1].x];
	zx[root].y = zx[root<<1|1].y | s[zx[root<<1|1].t][zx[root<<1].y];
	return ;
}

void build(int l,int r,int root=1)
{
	zx[root].l = l;
	zx[root].r = r;
	if(l==r)
	{
		zx[root].x = zx[root].y = zx[root].h = 1 << get(a[l]);
		zx[root].t = get(a[l]);
		return ;
	}
	else
	{
		int mid = (l+r)/2;
		build(l,mid,root<<1);
		build(mid+1,r,root<<1|1);
		up(root);
		return ;
	}	
}

int rex,rey,reh,ret;
int nowx,nowy,nowh,nowt;

void find(int l,int r,int root=1)
{
	if(l<=zx[root].l && r>=zx[root].r)
	{
		ret = get(nowt+zx[root].t);
		reh = nowh | zx[root].h;		
		reh |= f[nowy][zx[root].x];
		rex = nowx | s[nowt][zx[root].x];	
		rey = zx[root].y | s[zx[root].t][nowy];
		nowx = rex;	
		nowy = rey;
		nowh = reh;
		nowt = ret;	
		return ;
	}
	else
	{
		if(l<=zx[root<<1].r)
		{
			find(l,r,root<<1);
		}
		if(r>=zx[root<<1|1].l)
		{	
			find(l,r,root<<1|1);		
		}
		return ;
	}	
}

void init()
{
	int temp;
	for(int i=0;i<maxz;i++)
	{
		for(int j=0;j<maxz;j++)
		{
			temp = 0;
			for(int x=0;x<=9;x++)	
			{	
				if(!(i&(1<<x)))
					continue;
				for(int y=0;y<=9;y++)
				{
					if(!(j&(1<<y))) 
						continue;
		
					temp |= 1<<get(x+y);
				}
			}
			f[i][j]=temp;
		}
	}
	for(int i=0;i<=9;i++)
	{
		for(int j=0;j<maxz;j++)
		{
			temp = 0;
			for(int x=0;x<=9;x++)
			{
				if(j&(1<<x))
				{
					temp|=1<<get(i+x);
				}
			}
			s[i][j]=temp;
			assert(s[0][j]==j);
		}	
	}
	return ;
}

int main()
{
	init();
	int T;
	cin>>T;
	for(int tt=1;tt<=T;tt++)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			SS(a[i]);
		}
		build(1,n);
		cin>>c;
		int now,to;
		vector<int>v;
		if(tt>1)	
		{
			cout<<endl;
		}
		cout<<"Case #"<<tt<<":"<<endl;
		for(int i=1;i<=c;i++)
		{	
			SS(now);
			SS(to);
			rex=rey=reh=ret=nowx=nowy=nowt=nowh=0;
			find(now,to);	
			v.clear();
			for(int x=0;x<=9;x++)
			{	
				if(reh & (1<<x))
				{
					v.pb(x);
				}
			}
			sort(v.begin(),v.end());
			reverse(v.begin(),v.end());
			for(int i=1;i<=5;i++)
			{	
				v.pb(-1);
			}
			for(int i=0;i<=3;i++)
			{
				printf("%d ",v[i]);
			}
			printf("%d\n",v[4]);
		}
	}
	return 0;
}