Wine Factory (Easy Version) (Codeforces 1919F1)
Tags: Greedy, data structures

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$c_i$$$ and $$$z$$$. You can make hacks only if both versions of the problem are solved.There are three arrays $$$a$$$, $$$b$$$ and $$$c$$$. $$$a$$$ and $$$b$$$ have length $$$n$$$ and $$$c$$$ has length $$$n-1$$$. Let $$$W(a,b,c)$$$ denote the liters of wine created from the following process.Create $$$n$$$ water towers. The $$$i$$$-th water tower initially has $$$a_i$$$ liters of water and has a wizard with power $$$b_i$$$ in front of it. Furthermore, for each $$$1 \le i \le n - 1$$$, there is a valve connecting water tower $$$i$$$ to $$$i + 1$$$ with capacity $$$c_i$$$.For each $$$i$$$ from $$$1$$$ to $$$n$$$ in this order, the following happens:   The wizard in front of water tower $$$i$$$ removes at most $$$b_i$$$ liters of water from the tower and turns the removed water into wine.  If $$$i \neq n$$$, at most $$$c_i$$$ liters of the remaining water left in water tower $$$i$$$ flows through the valve into water tower $$$i + 1$$$. There are $$$q$$$ updates. In each update, you will be given integers $$$p$$$, $$$x$$$, $$$y$$$ and $$$z$$$ and you will update $$$a_p := x$$$, $$$b_p := y$$$ and $$$c_p := z$$$. After each update, find the value of $$$W(a,b,c)$$$. Note that previous updates to arrays $$$a$$$, $$$b$$$ and $$$c$$$ persist throughout future updates.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 5\cdot 10^5$$$, $$$1 \le q \le 5\cdot 10^5$$$) — the number of water towers and the number of updates.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the number of liters of water in water tower $$$i$$$.The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — the power of the wizard in front of water tower $$$i$$$.The fourth line contains $$$n - 1$$$ integers $$$c_1, c_2, \ldots, c_{n - 1}$$$ ($$$c_i \color{red}{=} 10^{18}$$$) — the capacity of the pipe connecting water tower $$$i$$$ to $$$i + 1$$$.Each of the next $$$q$$$ lines contains four integers $$$p$$$, $$$x$$$, $$$y$$$ and $$$z$$$ ($$$1 \le p \le n$$$, $$$0 \le x, y \le 10^9$$$, $$$z \color{red}{=} 10^{18}$$$) — the updates done to arrays $$$a$$$, $$$b$$$ and $$$c$$$.Note that $$$c_n$$$ does not exist, so the value of $$$z$$$ does not matter when $$$p = n$$$.

Output: Print $$$q$$$ lines, each line containing a single integer representing $$$W(a, b, c)$$$ after each update.

Note: The first update does not make any modifications to the arrays.   When $$$i = 1$$$, there are $$$3$$$ liters of water in tower 1 and $$$1$$$ liter of water is turned into wine. The remaining $$$2$$$ liters of water flow into tower 2.  When $$$i = 2$$$, there are $$$5$$$ liters of water in tower 2 and $$$4$$$ liters of water is turned into wine. The remaining $$$1$$$ liter of water flows into tower 3.  When $$$i = 3$$$, there are $$$4$$$ liters of water in tower 3 and $$$2$$$ liters of water is turned into wine. The remaining $$$2$$$ liters of water flows into tower 4.  When $$$i = 4$$$, there are $$$5$$$ liters of water in tower 4. All $$$5$$$ liters of water are turned into wine. Hence, $$$W(a,b,c)=1 + 4 + 2 + 5 = 12$$$ after the first update.The second update modifies the arrays to $$$a = [3, 5, 3, 3]$$$, $$$b = [1, 1, 2, 8]$$$, and $$$c = [10^{18}, 10^{18}, 10^{18}]$$$.  When $$$i = 1$$$, there are $$$3$$$ liters of water in tower 1 and $$$1$$$ liter of water is turned into wine. The remaining $$$2$$$ liters of water flow into tower 2.  When $$$i = 2$$$, there are $$$7$$$ liters of water in tower 2 and $$$1$$$ liter of water is turned into wine. The remaining $$$6$$$ liters of water flow into tower 3.  When $$$i = 3$$$, there are $$$9$$$ liters of water in tower 3 and $$$2$$$ liters of water is turned into wine. The remaining $$$7$$$ liters of water flow into tower 4.  When $$$i = 4$$$, there are $$$10$$$ liters of water in tower 4. Only $$$8$$$ liters of water is turned into wine. Hence, $$$W(a,b,c)=1 + 1 + 2 + 8 = 12$$$ after the second update.The third update modifies the arrays to $$$a = [3, 5, 0, 3]$$$, $$$b = [1, 1, 0, 8]$$$, and $$$c = [10^{18}, 10^{18}, 10^{18}]$$$.  When $$$i = 1$$$, there are $$$3$$$ liters of water in tower 1 and $$$1$$$ liter of water is turned into wine. The remaining $$$2$$$ liters of water flow into tower 2.  When $$$i = 2$$$, there are $$$7$$$ liters of water in tower 2 and $$$1$$$ liter of water is turned into wine. The remaining $$$6$$$ liters of water flow into tower 3.  When $$$i = 3$$$, there are $$$6$$$ liters of water in tower 3 and $$$0$$$ liters of water is turned into wine. The remaining $$$6$$$ liters of water flow into tower 4.  When $$$i = 4$$$, there are $$$9$$$ liters of water in tower 4. Only $$$8$$$ liters of water is turned into wine. Hence, $$$W(a,b,c)=1 + 1 + 0 + 8 = 10$$$ after the third update.

Sample Inputs:
4 3
3 3 3 3
1 4 2 8
1000000000000000000 1000000000000000000 1000000000000000000
4 3 8 1000000000000000000
2 5 1 1000000000000000000
3 0 0 1000000000000000000

5 5
10 3 8 9 2
3 4 10 8 1
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
5 4 9 1000000000000000000
1 1 1 1000000000000000000
2 7 4 1000000000000000000
4 1 1 1000000000000000000
1 8 3 1000000000000000000

Sample Outputs:
12
12
10

34
25
29
21
27

Solution (Python):
from sys import stdin
(n, q) = map(int, stdin.readline().split())
amount = list(map(int, stdin.readline().split()))
strength = list(map(int, stdin.readline().split()))
throughput = list(map(int, stdin.readline().split()))
throughput.append(0)
wine = [0] * n
for i in range(n):
    w = min(amount[i], strength[i])
    amount[i] -= w
    strength[i] -= w
    wine[i] += w
    amount[i] = min(amount[i], throughput[i])
    throughput[i] -= amount[i]
n2 = 1
while n2 < n:
    n2 <<= 1
for l in [amount, strength, wine, throughput]:
    l.extend([0] * (n2 - n))
    l[0:0] = [0] * (n2 - 1)
for i in reversed(range(n2 - 1)):
    l = 2 * i + 1
    r = l + 1
    dw = min(amount[l], strength[r])
    wine[i] = wine[l] + wine[r] + dw
    db = min(strength[r] - dw, throughput[l])
    strength[i] = strength[l] + db
    da = min(amount[l] - dw, throughput[r])
    amount[i] = amount[r] + da
    throughput[i] = min(throughput[l] - db, throughput[r] - da)
for query_id in range(q):
    (p, a, b, c) = map(int, stdin.readline().split())
    i = p + n2 - 2
    w = min(a, b)
    wine[i] = w
    amount[i] = min(a - w, c)
    strength[i] = b - w
    throughput[i] = c - amount[i]
    while i > 0:
        i = i - 1 >> 1
        l = 2 * i + 1
        r = l + 1
        dw = min(amount[l], strength[r])
        wine[i] = wine[l] + wine[r] + dw
        db = min(strength[r] - dw, throughput[l])
        strength[i] = strength[l] + db
        da = min(amount[l] - dw, throughput[r])
        amount[i] = amount[r] + da
        throughput[i] = min(throughput[l] - db, throughput[r] - da)
    print(wine[0])

Solution (Python):
from __future__ import print_function
from math import *
from collections import defaultdict, deque
import os
import random
import sys
from io import BytesIO, IOBase
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def main():
    pass
BUFSIZE = 8192

def lcm(a, b):
    return a * b // gcd(a, b)

def ceilDiv(a, b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

class myDict:

    def __init__(self, func):
        self.RANDOM = random.randint(0, 1 << 32)
        self.default = func
        self.dict = {}

    def items(self):
        return [(i ^ self.RANDOM, j) for (i, j) in self.dict.items()]

    def __getitem__(self, key):
        myKey = self.RANDOM ^ key
        if myKey not in self.dict:
            self.dict[myKey] = self.default()
        return self.dict[myKey]

    def __setitem__(self, key, item):
        myKey = self.RANDOM ^ key
        self.dict[myKey] = item

    def __iter__(self):
        return iter((i ^ self.RANDOM for i in self.dict))

    def __contains__(self, key):
        return key ^ self.RANDOM in self.dict

    def __repr__(self):
        return repr({i ^ self.RANDOM: j for (i, j) in self.dict.items()})

class mySet:

    def __init__(self):
        self.random = random.randint(0, 1 << 32)
        self.set = set()

    def add(self, key):
        self.set.add(key ^ self.random)

    def remove(self, key):
        self.set.remove(key ^ self.random)

    def __contains__(self, key):
        return key ^ self.random in self.set

    def __iter__(self):
        return iter((i ^ self.random for i in self.set))

    def __len__(self):
        return len(self.set)

    def __repr__(self):
        s = set()
        for item in self.set:
            s.add(item ^ self.random)
        return repr(s)
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s)])

def invr():
    return map(int, input().split())

class SegmentTree:

    def __init__(self, n, default=0):
        """"""
        self._default = default
        self._len = n
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.a = [default] * (2 * _size)
        self.b = [0] * (2 * _size)
        self.out = [0] * (2 * _size)
        self.ans = [0] * (2 * _size)

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        (newa, newb) = value
        idx += self._size
        self.a[idx] = newa
        self.b[idx] = newb
        self.ans[idx] = min(newb, newa)
        self.out[idx] = max(0, newa - newb)
        idx >>= 1
        while idx:
            self.a[idx] = self.a[2 * idx] + self.a[2 * idx + 1]
            self.b[idx] = self.b[2 * idx] + self.b[2 * idx + 1]
            outflow = self.out[2 * idx]
            tota = self.a[2 * idx + 1]
            totb = self.b[2 * idx + 1]
            totans = self.ans[2 * idx + 1]
            if totans == totb:
                self.ans[idx] = self.ans[2 * idx] + totans
                self.out[idx] = self.out[2 * idx + 1] + outflow
            else:
                diff = totb - totans
                self.ans[idx] = self.ans[2 * idx] + totans + min(diff, outflow)
                self.out[idx] = self.out[2 * idx + 1] + max(0, outflow - min(diff, outflow))
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
(n, q) = invr()
a = inlt()
b = inlt()
c = inlt()
s = SegmentTree(n)
for i in range(n):
    s[i] = (a[i], b[i])
for i in range(q):
    (p, x, y, z) = invr()
    s[p - 1] = (x, y)
    print(s.ans[1])

Solution (Python):
from sys import stdin, stdout

class LazySegmentTree:

    def __init__(self, data, default=0, func=min):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """"""
        (q, self._lazy[idx]) = (self._lazy[idx], 0)
        self._lazy[2 * idx] += q
        self._lazy[2 * idx + 1] += q
        self.data[2 * idx] += q
        self.data[2 * idx + 1] += q

    def _update(self, idx):
        """"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1]) + self._lazy[idx]
            idx >>= 1

    def add(self, start, stop, value):
        """"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
            start >>= 1
            stop >>= 1
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        """"""
        start += self._size
        stop += self._size
        self._update(start)
        self._update(stop - 1)
        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'LazySegmentTree({0})'.format(self.data)
(n, q) = [int(x) for x in stdin.readline().split()]
a = [int(x) for x in stdin.readline().split()]
b = [int(x) for x in stdin.readline().split()]
c = [int(x) for x in stdin.readline().split()]
diff = [0]
for i in range(n):
    diff.append(diff[-1] + a[i] - b[i])
diff = LazySegmentTree(diff)
b_sum = sum(b)
for _ in range(q):
    (p, x, y, z) = [int(xx) for xx in stdin.readline().split()]
    diff.add(p, n + 1, x - y - a[p - 1] + b[p - 1])
    b_sum -= b[p - 1]
    b_sum += y
    a[p - 1] = x
    b[p - 1] = y
    answer = diff.query(0, n + 1) + b_sum
    stdout.write(str(answer) + '\n')