5355 : B56 - 회문 쿼리
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
회문이란 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 말합니다.
길이가 $ N $ 인 문자열 $ S $ 가 주어집니다. 다음 $ Q $ 개의 쿼리에 답하십시오.
$ i $ 번째 쿼리: $ S[L_i, R_i]$ 는 회문인가?
여기서 $ S[l, r]$ 은 $ S $ 의 $ l $ 번째 문자부터 $ r $ 번째 문자까지의 연속 부분 문자열을 의미합니다.
[제약 조건]
• $N, Q, L_i, R_i$ 는 정수입니다.
• $S$ 는 영소문자로 이루어진 문자열입니다.
• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $|S| = N$
• $1 \le L_i \le R_i \le N$
길이가 $ N $ 인 문자열 $ S $ 가 주어집니다. 다음 $ Q $ 개의 쿼리에 답하십시오.
$ i $ 번째 쿼리: $ S[L_i, R_i]$ 는 회문인가?
여기서 $ S[l, r]$ 은 $ S $ 의 $ l $ 번째 문자부터 $ r $ 번째 문자까지의 연속 부분 문자열을 의미합니다.
[제약 조건]
• $N, Q, L_i, R_i$ 는 정수입니다.
• $S$ 는 영소문자로 이루어진 문자열입니다.
• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $|S| = N$
• $1 \le L_i \le R_i \le N$
입력 설명
첫째 줄에 $ N, Q $ 가 주어집니다.
둘째 줄에 문자열 $ S $ 가 주어집니다.
이후 $ Q $ 개 줄에 각 쿼리 $ L_i, R_i $ 가 주어집니다.
둘째 줄에 문자열 $ S $ 가 주어집니다.
이후 $ Q $ 개 줄에 각 쿼리 $ L_i, R_i $ 가 주어집니다.
출력 설명
각 쿼리에 대해 회문이면 `Yes`, 아니면 `No`를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
11 3
mississippi
5 8
6 10
2 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
Yes
No
Yes도움
$ 1 $ 번째 쿼리에서는 $ S[5, 8] = issi $ 가 회문인지 묻고 있습니다. 이는 회문이므로 Yes를 출력합니다.