巨石迷阵

问题描述

听说这片土地埋藏着什么秘密，来到这片土地的人不计其数，有人说这里财宝无数，也有人说这里是上古文明留下来的遗迹。小 L 收集情报和资料很久了，只身一人历经千辛万苦终于来到了这片地域的中心地带。突然，四周升起许多巨石，不出所料，面前的正是巨石迷阵。

你面前有 $n$ 块巨石排成一行，每个上面有一个大写字母。
接下来有 $m$ 个询问，每一个询问包含两个数字 $l,r$ ，对于每个询问，你需要回答这个处于区间 $[l,r]$ 的石块上的字母是否每一个英文字母都至少出现了一次。

输入格式

第一行一个整数 $n$ , $n\le5\times10^5$
第二行，一个长度为 $n$ 的字符串
第三行，一个整数 $m$, $m\le5\times10^5$
接下来的 $m$ 行，每行两个整数表示 $l,r,1\le l\le r\le n$

输出格式

输出包含 $m$ 行，每行一个 $\text{YES}$ ,或者 $\text{NO}$ 。
分别表示是否每个字母都至少出现一次。

样例输入

30
AAABCDEFGHIJKLMNOPQRSTUVWXYZAA
5
1 26
2 27
3 28
4 29
5 30

样例输出

NO
NO
YES
YES
NO

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

int a[26][500005];

inline bool check(int l, const int& r) {
    --l;
    for (int i = 0; i < 26; ++i) {
        if (a[i][r] - a[i][l] == 0)
            return false;
    }
    return true;
}

int main() {
    memset(a, 0, sizeof(a));
    int n, m, now, l, r;
    string s;
    cin >> n;
    cin >> s;
    cin >> m;
    for (int i = 0; i < s.length(); ++i) {
        now = i + 1;
        for (int j = 0; j < 26; ++j) {
            a[j][now] = a[j][i];
        }
        ++a[s[i] - 'A'][now];
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &l, &r);
        if (check(l, r))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}