-
-
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') | |
If you see the main function, you will see when do the query, it actually call the query(a, b + 1). So the idea of query function is to get minimum element from the range [a, b), notice it's a half closed and half open range, so if you want to get minimum element from range [1, 1], you need to call query(1, 2).
For the sys.maxint, it is just used as a value for null in RMQ, so if you want to query the minimun value, you need to use sys.maxint, and if you want to query maximum value in a range, you need to use sys.minint. It's just like if there is no answer for your query, the maximum value is returned, so for example query(1, 1) is actually call the function on an empty range[1, 1), so it will return sys.maxint.
Maybe it's also misleading in the example, since I used one self.inf and sys.maxint, I think you can think them as the same thing. It's just a null(maximum) value in the system.
Thank you for the explanation!
In a more general case, is it possible to change the value into a node with a cmp key?
Sorry I don't fully understand your question, could you please give some more details description of the problem? What do you mean to change the node with cmp key? Is the cmp key also used as compare field for querying?
Sure!
A simple case is not only return the minimum value but also the index of that value in the original array.
I changed the code into the following,
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])
I tried on some problems but not sure about the correctness. Does it make sense to you?
Yeah, it make sense to me. Basically you just store a two element tuple(index, value) in each node and the first one is index, and the second one is the value to compare for the operation, right?
Although I do not fully test your code, but it make sense for me.
If you are not sure for the correctness of the program, I would suggest you write a naive version for the RMQ(like scan range [a, b) in linear time to found the minimum one, make sure to have the same logic if there are equal items in the range, like return the leftmost or the rightmost in both linear one and RMQ one) as golden standard(make sure you don't have bug in the linear version, that would be much easy), and then write a random generator for both the two program and compare output for each step.
Thank you for the nice discussion! I learned a lot!
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):
Thanks for the code! It works!
I have a question, in this code, one has to assume the query input
a < b.For example:
Is that the expected behavior?