-
-
Save m00nlight/1f226777a49cfc40ed8f to your computer and use it in GitHub Desktop.
| import sys | |
| import itertools | |
| class RMQ: | |
| def __init__(self, n): | |
| self.sz = 1 | |
| self.inf = (1 << 31) - 1 | |
| while self.sz <= n: self.sz = self.sz << 1 | |
| self.dat = [self.inf] * (2 * self.sz - 1) | |
| def update(self, idx, x): | |
| idx += self.sz - 1 | |
| self.dat[idx] = x | |
| while idx > 0: | |
| idx = (idx - 1) >> 1 | |
| self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2]) | |
| def query(self, a, b): | |
| return self.query_help(a, b, 0, 0, self.sz) | |
| def query_help(self, a, b, k, l, r): | |
| if r <= a or b <= l: | |
| return sys.maxint | |
| elif a <= l and r <= b: | |
| return self.dat[k] | |
| else: | |
| return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1), | |
| self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r)) | |
| if __name__ == '__main__': | |
| line = sys.stdin.readline() | |
| n, q = line.split() | |
| n, q = int(n), int(q) | |
| rmq = RMQ(n) | |
| for i in range(q): | |
| line = sys.stdin.readline() | |
| op, a, b = line.split() | |
| op, a, b = int(op), int(a), int(b) | |
| if op == 0: | |
| rmq.update(a, b) | |
| else: | |
| sys.stdout.write(str(rmq.query(a, b + 1)) + '\n') | |
Thank you for the nice discussion! I learned a lot!
You're welcome
One more thing, when I apply the RMQ to a list of long array with the same value, in practice, 5000 in length.
I will get RecursionError: maximum recursion depth exceeded.
I guess it's common error for python, I am trying to find a way to get around this without changing the recursion limit.
if __name__ == '__main__':
rmq = RMQ(5000)
for idx in range(0, 5000):
rmq.update(idx, 10)
print(rmq.query(0, 1000))Normally that should not happen, I check the default python recursion limit is 1000, it should be enough for most cases. I use the above program to test and don't get the exception, could you please paste your program which causes this problem?
I am trying the problem https://codeforces.com/problemset/problem/448/C#
The code is
import sys
import itertools
# sys.setrecursionlimit(10**6)
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
while self.sz <= n:
self.sz = self.sz << 1
self.dat = [[None, self.inf] for i in range(2 * self.sz - 1)]
def update(self, idx, x):
old_idx = idx
idx += self.sz - 1
self.dat[idx] = [old_idx, x]
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1],
self.dat[idx * 2 + 2],
key=lambda x: x[1])
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return (0, sys.maxsize)
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r) >> 1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r),
key=lambda x: x[1])
def solve_l_r(left, right, height):
if left > right:
return 0
min_right, min_height = rmq.query(left, right + 1)
res = min(right - left + 1,
min_height - height + \
solve_l_r(left, min_right - 1, min_height) + \
solve_l_r(min_right + 1, right, min_height))
return res
def painting_fences():
for i, j in enumerate(case_n):
rmq.update(i, j)
return solve_l_r(0, len(case_n) - 1, 0)
if __name__ == '__main__':
num = int(sys.stdin.readline())
case_n = list(map(int, sys.stdin.readline().split()))
rmq = RMQ(num)
assert len(case_n) == num
print(painting_fences())
Hmm, seems the stack for python recursion is really shallow. And when all the number are the same, the recursive call solve_l_r become a list call for each element(since all element are the same, so the recursive call depth problem is not from the RMQ query), and it seems on codeforce, they don't allow python to do recursive call to go deep. But for C/C++, it is easy to do a recursive call for that depth.
https://codeforces.com/blog/entry/16905
IMO, the recursion limit(level of thousands) of python is really small compare to language like C/C++ on codeforces. But one way to handle this is to handle the call stack manually instead of letting the python to handle the call stack. Like the following accept program, so the allocation will happen on heap space instead of stack space. And since the RMQ structure is a complete binary tree, so the upper boundary of recursive call is bounded to O(logN).
import sys
import itertools
from random import randint
# sys.setrecursionlimit(10**6)
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
while self.sz <= n:
self.sz = self.sz << 1
self.dat = [[None, self.inf] for i in range(2 * self.sz - 1)]
def update(self, idx, x):
old_idx = idx
idx += self.sz - 1
self.dat[idx] = [old_idx, x]
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1],
self.dat[idx * 2 + 2],
key=lambda x: x[1])
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return (0, sys.maxsize)
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r) >> 1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r),
key=lambda x: x[1])
def solve_l_r(left, right, height):
if left > right:
return 0
min_right, min_height = rmq.query(left, right + 1)
res = min(right - left + 1,
min_height - height + \
solve_l_r(left, min_right - 1, min_height) + \
solve_l_r(min_right + 1, right, min_height))
return res
def painting_fences():
for i, j in enumerate(case_n):
rmq.update(i, j)
answer = {}
stack = [{"left": 0, "right": len(case_n) - 1, "height": 0, "recursive": True, "calc": False}]
while stack:
elem = stack.pop()
left, right, isRecursive, height, isCalc = elem["left"], elem["right"], elem["recursive"], elem["height"], elem["calc"]
if (left > right):
answer[(left, right)] = 0
else:
min_right, min_height = rmq.query(left, right + 1)
if isCalc:
answer[(left, right)] = min(right - left + 1,
min_height - height + answer[(left, min_right -1)] + answer[(min_right + 1, right)])
elif isRecursive:
stack.append({"left": left, "right": right, "height": height, "recursive": False, "calc": True})
stack.append({"left": left, "right": min_right - 1, "height": min_height, "recursive": True, "calc": False})
stack.append({"left": min_right + 1, "right": right, "height": min_height, "recursive": True, "calc": False})
return answer[(0, len(case_n) - 1)]
if __name__ == '__main__':
num = int(sys.stdin.readline())
case_n = list(map(int, sys.stdin.readline().split()))
# num = 5000
# case_n = [10000 for i in range(num)]
rmq = RMQ(num)
assert len(case_n) == num
print(painting_fences())
Thank you! Nice coding!
I tried to use generator to resolve the problem but failed. It's not working as explained on stackoverflow.
Hi,
I don't suppose you have some example data that this works with, I would like to use it for a project but am unsure how to run it. Is it possible to get it to take in a normal array without reading from a file?
Any help would be greatly appreciated :)
Hi,
I don't suppose you have some example data that this works with, I would like to use it for a project but am unsure how to run it. Is it possible to get it to take in a normal array without reading from a file?
Any help would be greatly appreciated :)
Hi Joshua,
Both the original code and the snippe for the codeforce example I pasted in comment use standard input(so when you run the program, you can enter the input from the console). Or you can use something like tho following to initialize the RMQ structure from a array.
if __name__ == '__main__':
rmq = RMQ(10)
data = [1, 2, 5, 3, 4, 2, 1, 5, 3, 2]
for idx, value in enumerate(data):
rmq.update(idx, value)
Great code, I am usually needing one RMQ implementation for some leetcode problems. I just used it for this problem btw (which is not the fastest for that problem, but I was curious in solving it with RMQ):
Thank you for the nice discussion! I learned a lot!