import sys
from bisect import bisect_right
class SegTree:
def __init__(self, n, mod):
self.n = n
self.mod = mod
self.N = 1
while self.N < n:
self.N <<= 1
self.segs = [[] for _ in range(2 * self.N)]
self.add = [[] for _ in range(2 * self.N)]
def build(self, v, tl, tr, a):
if tl + 1 == tr:
if tl < self.n:
self.segs[v] = [(0, a[tl] - 1), (a[tl], self.mod - 1)]
self.add[v] = [a[tl] + 1 if a[tl] + 1 < self.mod else 0, a[tl]]
else:
self.segs[v] = [(0, self.mod - 1)]
self.add[v] = [0]
return
m = tl + (tr - tl) // 2
self.build(2 * v, tl, m, a)
self.build(2 * v + 1, m, tr, a)
for i in range(len(self.segs[2 * v])):
l, r = self.segs[2 * v][i]
nxt = l + self.add[2 * v][i]
if nxt >= self.mod:
nxt -= self.mod
j = bisect_right(self.segs[2 * v + 1], (nxt, self.mod)) - 1
while self.segs[2 * v + 1][j][1] - nxt < r - l:
self.segs[v].append((l, l + self.segs[2 * v + 1][j][1] - nxt))
self.add[v].append(self.add[2 * v][i] + self.add[2 * v + 1][j])
if self.add[v][-1] >= self.mod:
self.add[v][-1] -= self.mod
l = self.segs[v][-1][1] + 1
nxt = l + self.add[2 * v][i]
if nxt >= self.mod:
nxt -= self.mod
j += 1
if j == len(self.segs[2 * v + 1]):
j = 0
self.segs[v].append((l, r))
self.add[v].append(self.add[2 * v][i] + self.add[2 * v + 1][j])
if self.add[v][-1] >= self.mod:
self.add[v][-1] -= self.mod
def build_tree(self, a):
self.build(1, 0, self.N, a)
def query(self, v, tl, tr, l, r, rocks):
if l <= tl and tr <= r:
pos = bisect_right(self.segs[v], (rocks, self.mod)) - 1
rocks += self.add[v][pos]
if rocks >= self.mod:
rocks -= self.mod
return rocks
m = tl + (tr - tl) // 2
if l < m:
rocks = self.query(2 * v, tl, m, l, r, rocks)
if m < r:
rocks = self.query(2 * v + 1, m, tr, l, r, rocks)
return rocks
def query_tree(self, l, r, rocks):
if l >= r:
return rocks
return self.query(1, 0, self.N, l, r, rocks)
def solve():
n, m = map(int, input().split())
s = input()
posBPref, posRSuf = [], []
for i in range(n):
if s[i] == 'B':
posBPref.append(i)
else:
posRSuf.append(i)
posRSuf.reverse()
posBPref.append(n)
posRSuf.append(-1)
a = list(map(int, input().split()))
pref = [0] * (m + 1)
prefLeq = [[0 for _ in range(maxlog)] for _ in range(m + 1)]
prefReq = [[0 for _ in range(maxlog)] for _ in range(m + 1)]
cntReq = [[0 for _ in range(maxlog)] for _ in range(m + 1)]
for i in range(m):
pref[i + 1] = pref[i] + a[i]
for k in range(maxlog):
prefLeq[i + 1][k] = prefLeq[i][k] + (a[i] <= (1 << k)) * a[i]
prefReq[i + 1][k] = prefReq[i][k] + (a[i] > (n - (1 << k))) * a[i]
cntReq[i + 1][k] = cntReq[i][k] + (a[i] > (n - (1 << k)))
st = SegTree(m, n + 1)
st.build_tree(a)
q = int(input())
for _ in range(q):
l, r = map(int, input().split())
l -= 1
prefR = posBPref[0]
sufB = n - posRSuf[0] - 1
addPref = 0
addSuf = 0
if prefR == 0 and sufB == 0:
makeStep(a[l], prefR, sufB, addPref, addSuf)
l += 1
while not collided(addPref, addSuf) and l < r:
left, right = l, r + 1
while right - left > 1:
mid = left + (right - left) // 2
if hasBad(prefR, sufB, l, mid):
right = mid
else:
left = mid
l = completeTillCollide(prefR, sufB, addPref, addSuf, l, left)
if not collided(addPref, addSuf) and l < r:
makeStep(a[l], prefR, sufB, addPref, addSuf)
l += 1
ans = 0
if collided(addPref, addSuf):
ans = st.query_tree(l, r, prefR)
else:
ans = len(posRSuf) - 1 + addPref - addSuf
print(ans)
if __name__ == "__main__":
ios_base_sync_with_stdio = False
cin_tie = False
cout_tie = False
maxlog = 17
maxn = 120001
Log = [-1, 0] + [0] * (maxn - 2)
for i in range(2, maxn):
Log[i] = Log[i >> 1] + 1
T = 1
for _ in range(T):
solve()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
21644 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
21644 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
21644 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
21900 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
21900 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
21900 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
21644 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
