Editing 2016 Jan Platinum Problem 2 Mowing the Field (section)

=== Python ===
<pre>
import sys
from collections import defaultdict

MAXN = 1 << 17
MAXV = 1 << 30

class Node:
    def __init__(self):
        self.val = 0
        self.child = [None, None]

    def get_child(self, c):
        if self.child[c] is None:
            self.child[c] = Node()
        return self.child[c]

    def add(self, x, v, lo, hi):
        self.val += v
        if hi - lo == 1:
            return
        mid = (lo + hi) // 2
        if x < mid:
            self.get_child(0).add(x, v, lo, mid)
        else:
            self.get_child(1).add(x, v, mid, hi)

    def query(self, a, b, lo, hi):
        if a <= lo and hi <= b:
            return self.val
        elif hi <= a or b <= lo:
            return 0
        mid = (lo + hi) // 2
        return (self.child[0].query(a, b, lo, mid) if self.child[0] else 0) + \
               (self.child[1].query(a, b, mid, hi) if self.child[1] else 0)


bit = defaultdict(Node)

def bit_add(x, y, v):
    j = y | MAXN
    while j < (MAXN << 1):
        bit[j ^ MAXN].add(x, v, 0, MAXV)
        j += j & -j

def bit_get(x0, x1, y):
    ret = 0
    j = y - 1
    while j != 0:
        ret += bit[j].query(x0, x1, 0, MAXV)
        j &= j - 1
        if j == 0:
            break
    return ret

def main():
    # Reads input, processes it, and writes output.
    # Implementation needed here.

if __name__ == "__main__":
    main()

</pre>


[[Category:Yearly_2015_2016]]
[[Category:Platinum]]
[[Category:Geometry]]
[[Category:Segment Tree]]
[[Category:Sweep Line]]