Submission #3094392

---

Source Code Expand

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
#include <list>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

int i,j,k,l,m,n;
/////////////////////////////////////////////////////
#define INF 999999999
#define DUB 21 //>log2_505050

char s[505050];
int Q;

int sl;
int nextc[505050][30];
int nextdb[505050][DUB];


int main(){
    //文字列入力
    cin>>s;

    //データ作成
    for(sl=0;s[sl]!='\0';sl++);

    int C[30];
    //cout<<sl<<" "<<endl;
    for(j=0;j<27;j++){
        nextc[sl][j]=INF;
        C[j]=INF;
    }
    for(i=sl-1;i>=0;i--){
        for(j=0;j<27;j++){
            nextc[i][j]=INF;
        }
        int cc=s[i]-'a';
        nextc[i][cc]=i+1;
        int ci=nextc[nextc[i][cc]][cc];
        
        while(ci!=INF&&cc<26){
            cc++;
            nextc[i][cc]=ci;
            ci=nextc[nextc[i][cc]][cc];
        }
        if(cc==26){
            int idx=nextc[i][26];
            int cci=s[i]-'a';
            cc=0;
            while(cc<cci){
                nextc[i][cc]=nextc[idx][cc];
                cc++;
            }
        }
        /*
        cout<<"\n"<<i<<":"<<endl;
        for(j=0;j<27;j++){
            if(nextc[i][j]==INF)
                cout<< " ["<<j<< "]:-"; 
            else
                cout <<" ["<<j<< "]:" << nextc[i][j];
        }
        */
        
    }

    //ダブリング
    for(i=0;i<=sl;i++){
        nextdb[i][0]=nextc[i][26];
    }
    for(k=1;k<DUB;k++){
        for(i=0;i<=sl;i++){
            if(nextdb[i][k-1]!=INF){
                nextdb[i][k]=nextdb[nextdb[i][k-1]][k-1];
            }else{
                nextdb[i][k]=INF;
            }
            //cout<<" "<<k<<":"<<i<< nextdb[k][i]<<endl;
        }
    }   

    //検索
    cin>>Q;
    int l,r,lr;
    for(i=0;i<Q;i++){
        cin >> l >> r;
        l--;
        for(k=DUB-1;k>=0;k--){
            if(r>=nextdb[l][k]){
                l=nextdb[l][k];
                if(r==l)
                    break;
            }
        }
        if(l==r){
            cout<< "Yes"<<endl;
        }else{
            cout<<"No"<< endl;
        }
    }
    
    return 0;
}

Submission Info

Judge Result