https://codeforces.com/contest/1539/problem/B
시간 1초, 메모리 256MB
input :
- n q (1≤n≤100000, 1≤q≤100000)
- s (consisting of n lowercase letters of English letters.)
- l r (1≤l≤r≤n)
output :
- q lines: for each question print the length of the string obtained by Vasya.
- 각 질문에 대한 정답을 출력합니다.
조건 :
-
Each question is about a subsegment of the song starting from the l-th letter to the r-th letter
-
각 질문들은 노래의 부분적인 가사를 의미하는데 이 부분은 l에서 부터 r번째 글자를 의미합니다.
-
Vasya considers a substring made up from characters on this segment and repeats each letter in the subsegment k times, where k is the index of the corresponding letter in the alphabet.
-
Vasya는 부분적인 가사를 이용해서 각 문자를 k번 반복해서 새로운 문장을 만듭니다. 이 때 k는 각 알파벳의 순서를 의미 합니다.
-
예를 들어 a는 1, b 는 2, .... 해서 계속 증가합니다.
결국 해야 하는 것은 인덱스 l, r이 들어 왔을 때 몇 개의 알파벳으로 구성된 문장을 만드냐 라는 질문을 하는 것이다. 이미 알고 있는 정보로는 각 알파벳의 k를 알수 있다. 아스키 코드를 이용해서 97을 빼는것으로 이를 구할 수 있다.
그렇다면 각 문자의 등장횟수를 하나 하나씩 체크 할 것인가? 그렇게 될 경우 시간 복잡도가 터질 것이다. 고로 자료구조 시간에 많이 사용한 합 계산 하는 방법을 사용해야 한다.
for문 한 번을 통해서 0번째 인덱스에서 부터 각 인덱스 까지의 합을 저장하고 있는 배열을 만든다. k의 합을 저장하고 있어야 한다.
그 후 l, r이 들어 왔을 때 data[r] - data[l - 1]을 통해서 정답을 구하도록 하자.
l - 1을 해야 하니까 배열의 길이는 1 더 길어야 한다.
import sys
n, q = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()
data = [0] * (len(s) + 1)
for i in range(len(s)):
data[i + 1] = data[i] + ord(s[i]) - 96
for i in range(q):
l, r = map(int, sys.stdin.readline().split())
print(data[r] - data[l - 1])
