2016"百度之星" - 资格赛（Astar Round1） A

链接:http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=690&pid=1001

我用线段树过的~可能要注意a,b的关系

 #include<stdio.h>

 //#include<bits/stdc++.h>

 #include<string.h>

 #include<iostream>

 #include<math.h>

 #include<sstream>

 #include<set>

 #include<queue>

 #include<map>

 #include<vector>

 #include<algorithm>

 #include<limits.h>

 #define inf 0x7fffffff

 #define INFL 0x7fffffffffffffff

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define LL long long

 #define ULL unsigned long long

 const int N = ;

 const int MOD = ;

 using namespace std;

 int num[N];

 int ans;

 char c[N];

 struct node

 {

     int left;

     int right;

     int value;

 }tree[N*];

 void sum(int rt)

 {

     tree[rt].value = (tree[rt*].value*tree[rt*+].value)%MOD;

 }

 void build(int l,int r,int rt)

 {

     tree[rt].left=l;

     tree[rt].right=r;

     int m=(l+r)>>;

     if(l==r)

     {

         tree[rt].value=num[l];

         return;

     }

     build(lson);

     build(rson);

     tree[rt].value=(tree[rt*].value*tree[rt*+].value)%MOD;

 }

 void query(int l,int r,int rt)

 {

     if(l==tree[rt].left&&r==tree[rt].right)

     {

         ans=(ans*tree[rt].value)%MOD;

         return ;

     }

     int m=(tree[rt].left+tree[rt].right)>>;

      if(r<=m)

         query(l,r,rt*);

     else if(l>m)

         query(l,r,rt*+);

     else

     {

         query(l,m,rt*);

         query(m+,r,rt*+);

     }

 }

 int main()

 {

     int t;

     while(~scanf("%d",&t))

     {

         scanf("%s",c);

         int len=strlen(c);

         for(int i=;i<len;i++)

         {

             num[i+]=c[i]-;

         }

         build(,N,);

         for(int i=;i<t;i++)

         {

             ans=;

             int l,r;

             scanf("%d%d",&l,&r);

             if(l>r)

             {

                 swap(l,r);

             }

             query(l,r,);

             printf("%d\n",ans);

         }

     }

     return ;

 }