Submission #2076217

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 500010;

int tor[MN][27]; //26 for ""
int nx[20][MN];

int main() {
	string s;
	cin >> s;
	int n = s.size();

	rep(i, 27) tor[n][i] = MN;
	for (int i = n-1; i >= 0; --i) {
		int c = s[i] - 'a';
		tor[i][c] = i + 1;

		for (int j = c + 1; j < 27; ++j) {
			tor[i][j] = (tor[i][j-1] == MN ? MN : tor[tor[i][j-1]][j-1]);
		}

		nx[0][i] = tor[i][26];

		for (int j = 0; j < c; ++j) {
			tor[i][j] = (tor[i][26] == MN ? MN : tor[tor[i][26]][j]);
		}
	}

	rep(i, 19) {
		rep(j, n) {
			nx[i+1][j] = (nx[i][j] == MN ? MN : nx[i][nx[i][j]]);
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		--l;

		for (int i = 19; i >= 0; --i) {
			if (nx[i][l] < r) {
				l = nx[i][l];
			}
		}
		puts(nx[0][l] == r ? "Yes" : "No");
	}

	return 0;
}

Submission Info

Judge Result