Submission #75949322

---

Source Code Expand

#D
import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
S = input().strip()

#블럭 구성(Code, start, end, w)
blockinfo = [None]*N
blockinfo[0] = 0
block = []
start = 0
end = 0
code = 0
tmp = []
for i in range(1, N):
    if S[i] == S[i-1]:
        end += 1
        blockinfo[i] = code
    else:
        if S[i - 1] in 'RGB':
            block.append((code, start, end, (end - start + 1) // 2))
        else:
            block.append((code, start, end, 0))
            tmp.append(code)
        start = i
        end = i
        code += 1
        blockinfo[i] = code

if S[end] in 'RGB':
    block.append((code, start, end, (end - start + 1) // 2))
else:
    block.append((code, start, end, 0))
    tmp.append(code)

M = len(block)
isx = [False]*M
for i in tmp:
    isx[i] = True
s = [0]
for i in range(M):
    s.append(s[-1] + block[i][3])


for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    l, r = l-1, r-1
    lb = blockinfo[l]
    rb = blockinfo[r]
    if lb == rb and not isx[lb]:
        ans = (r - l + 1)//2
    else:
        if block[lb][1] < l:
            if not isx[lb]:
                ans += (block[lb][2] - l + 1)//2
            lb += 1
        if block[rb][2] > r:
            if not isx[rb]:
                ans += (r - block[rb][1] + 1)//2
            rb -= 1

        if lb <= rb:
            ans += s[rb + 1] - s[lb]

    print(ans)

Submission Info

Judge Result