1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def push(self, node, start, end):
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node] * (end - start + 1)
            if start != end:
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update_range(self, node, start, end, l, r, val):
        self.push(node, start, end)
        if start > r or end < l:
            return
        if l <= start and end <= r:
            self.lazy[node] += val
            self.push(node, start, end)
            return
        mid = (start + end) // 2
        self.update_range(2 * node, start, mid, l, r, val)
        self.update_range(2 * node + 1, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, start, end, idx):
        self.push(node, start, end)
        if start == end:
            return self.tree[node]
        mid = (start + end) // 2
        if idx <= mid:
            return self.query(2 * node, start, mid, idx)
        else:
            return self.query(2 * node + 1, mid + 1, end, idx)

def solve():
    # Input
    n, m, z = map(int, input().split())
    a = list(map(int, input().split()))
    v = [0] * n  # Initial values of leaves eaten per day

    # Segment tree for range updates
    seg_tree = SegmentTree(n)

    # Process modifications and queries
    operations = []
    for _ in range(m + z):
        op = list(map(int, input().split()))
        operations.append(op)

    answers = []
    for op in operations:
        op_type, p, x = op
        if op_type == 1:  # Modification
            seg_tree.update_range(1, 0, n - 1, 0, p - 1, x)
        else:  # Query
            total_leaves = 0
            for i in range(p):  # Check first p days
                if a[i] >= x:  # Tree x is visited if x <= a[i]
                    total_leaves += seg_tree.query(1, 0, n - 1, i)
            answers.append(total_leaves)

    # Output answers for queries
    for ans in answers:
        print(ans)

if __name__ == "__main__":
    solve()