Submission #2152290

---

Source Code Expand

#include <iostream>
#include <string>
using namespace std;

string S; int dp[500009][27], nex[500009][22];

int main() {
	cin >> S;
	for (int i = 0; i <= S.size(); i++) {
		for (int j = 0; j < 27; j++) dp[i][j] = (1 << 30);
	}
	for (int i = S.size() - 1; i >= 0; i--) {
		int A = S[i] - 'a';
		for (int j = 0; j <= 26; j++) {
			if (j == A) dp[i][j] = i + 1;
			if (j > A) {
				int cx = i + 1;
				for (int k = A; k < j; k++) {
					if (dp[cx][k] == (1 << 30)) { cx = (1 << 30); break; }
					cx = dp[cx][k];
				}
				dp[i][j] = cx;
			}
			if (j < A) {
				int cx = i + 1;
				for (int k = A; k < 26; k++) {
					if (dp[cx][k] == (1 << 30)) { cx = (1 << 30); break; }
					cx = dp[cx][k];
				}
				if (cx == (1 << 30)) continue;
				dp[i][j] = dp[cx][j];
			}
		}
	}
	for (int i = 0; i <= S.size(); i++) { for (int j = 0; j <= 20; j++) nex[i][j] = (1 << 30); }
	for (int i = 0; i < S.size(); i++) nex[i][0] = dp[i][26];
	for (int i = 0; i < 20; i++) {
		for (int j = 0; j < S.size(); j++) {
			if (nex[j][i] == (1 << 30)) continue;
			nex[j][i + 1] = nex[nex[j][i]][i];
		}
	}
	int Q; cin >> Q;
	for (int i = 1; i <= Q; i++) {
		int L, R; cin >> L >> R; L--; R--;
		int cx = L;
		for (int j = 20; j >= 0; j--) {
			if (nex[cx][j] <= R + 1) cx = nex[cx][j];
		}
		if (cx == R + 1) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Submission Info

Judge Result