BNUOJ52317 As Easy As Possible（树上倍增）-白红宇

BNUOJ52317 As Easy As Possible（树上倍增）

阅读量：7097 次

发布时间：2019-06-28

本文共 1575 字，大约阅读时间需要 5 分钟。

题意：

给你一个1e5长度的easy串（只含easy四个字母）

1e5个询问，每个询问一个区间l，r

问这个区间内easy的个数

思路：

当时还想预处理出最优的easy区间，然后lower_bound

wa了几发发现这样并不是最优的，然后就放弃了~

出题解后补了一个倍增

每个字母记录前面那个字母出现的位置，然后倍增

每次查询先找出距离r最近的那个'y'

然后直到找到l，统计出找到的字母的数量/4就是答案

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate
                 
                  inline void rd(T &x){ char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=1e5+10;char s[N];int py[N],fa[N][20],n,m,last[4],dep,l,r;int main(){ scanf("%s",s+1); rd(m); n=strlen(s+1); rep(i,1,n) { if(s[i]=='e') { fa[i][0]=last[3]; last[0]=i; } else if(s[i]=='a') { fa[i][0]=last[0]; last[1]=i; } else if(s[i]=='s') { fa[i][0]=last[1]; last[2]=i; } else { fa[i][0]=last[2]; last[3]=i; } py[i]=last[3]; } for(dep=1;1<
                  
                   <=n;dep++); rep(i,1,dep-1) rep(j,1,n) fa[j][i]=fa[fa[j][i-1]][i-1]; while(m--) { rd(l),rd(r); r=py[r]; int ans=1; dep(i,dep-1,0) if(fa[r][i]>=l) { r=fa[r][i]; ans+=1<