Colorful Operations (Codeforces 1638E)
Tags: Implement, data structures

You have an array $$$a_1,a_2, \dots, a_n$$$. Each element initially has value $$$0$$$ and color $$$1$$$. You are also given $$$q$$$ queries to perform:   Color $$$l$$$ $$$r$$$ $$$c$$$: Change the color of elements $$$a_l,a_{l+1},\cdots,a_r$$$ to $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$).  Add $$$c$$$ $$$x$$$: Add $$$x$$$ to values of all elements $$$a_i$$$ ($$$1 \le i \le n$$$) of color $$$c$$$ ($$$1 \le c \le n$$$, $$$-10^9 \le x \le 10^9$$$).  Query $$$i$$$: Print $$$a_i$$$ ($$$1 \le i \le n$$$). 

Input: The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — the length of array $$$a$$$ and the number of queries you have to perform.Each of the next $$$q$$$ lines contains the query given in the form described in the problem statement.

Output: Print the answers to the queries of the third type on separate lines.

Note: The first sample test is explained below. Blue, red and green represent colors $$$1$$$, $$$2$$$ and $$$3$$$ respectively.  

Sample Inputs:
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5

2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2

Sample Outputs:
2
5
3

7
7
8

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def add(s, t, x):
    (s, t) = (s + l1, t + l1)
    while s <= t:
        if s & 1:
            tree1[s] += x
            s += 1
        s >>= 1
        if not t & 1:
            tree1[t] += x
            t -= 1
        t >>= 1
    return

def get(i):
    i += l1
    ans = 0
    while i:
        ans += tree1[i]
        i >>= 1
    return ans

def update(i, x):
    i += l1
    tree2[i] = x
    i >>= 1
    while i:
        tree2[i] = max(tree2[2 * i], tree2[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree2[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree2[t])
            t -= 1
        t >>= 1
    return ans
(n, q) = map(int, input().split())
(u, v) = ([0] * (n + 5), [0] * (n + 5))
v[1] = 1
l1 = pow(2, (n + 5).bit_length())
l2 = 2 * l1
tree1 = [0] * l2
tree2 = [0] * l2
update(1, 1)
update(n + 1, n + 1)
nx = [0] * (n + 5)
(nx[1], nx[n + 1]) = (n, n + 1)
ans = []
for _ in range(q):
    q0 = list(input().rstrip().decode().split())
    if q0[0] == 'Color':
        (l, r, c) = (int(q0[1]), int(q0[2]), int(q0[3]))
        if not nx[l]:
            i = get_max(1, l - 1)
            v[l] = v[i]
            nx[l] = nx[i]
            nx[i] = l - 1
            update(l, l)
        if not nx[r + 1]:
            i = get_max(l, r)
            v[r + 1] = v[i]
            nx[r + 1] = nx[i]
            nx[i] = r
            update(r + 1, r + 1)
        i = l
        while i <= r:
            j = nx[i]
            add(i, j, u[v[i]])
            if i ^ l:
                update(i, 0)
            (nx[i], v[i]) = (0, 0)
            i = j + 1
        (nx[l], v[l]) = (r, c)
        add(l, r, -u[c])
    elif q0[0] == 'Add':
        (c, x) = (int(q0[1]), int(q0[2]))
        u[c] += x
    else:
        i = int(q0[1])
        c = v[get_max(1, i)]
        ans0 = get(i) + u[c]
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def add(s, t, x):
    (s, t) = (s + l1, t + l1)
    while s <= t:
        if s & 1:
            tree1[s] += x
            s += 1
        s >>= 1
        if not t & 1:
            tree1[t] += x
            t -= 1
        t >>= 1
    return

def get(i):
    i += l1
    ans = 0
    while i:
        ans += tree1[i]
        i >>= 1
    return ans

def update(i, x):
    i += l1
    tree2[i] = x
    i >>= 1
    while i:
        tree2[i] = max(tree2[2 * i], tree2[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree2[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree2[t])
            t -= 1
        t >>= 1
    return ans
(n, q) = map(int, input().split())
(u, v) = ([0] * (n + 5), [0] * (n + 5))
v[1] = 1
l1 = pow(2, (n + 5).bit_length())
l2 = 2 * l1
tree1 = [0] * l2
tree2 = [0] * l2
update(1, 1)
update(n + 1, n + 1)
nx = [0] * (n + 5)
(nx[1], nx[n + 1]) = (n, n + 1)
ans = []
for _ in range(q):
    q0 = list(input().rstrip().decode().split())
    if q0[0] == 'Color':
        (l, r, c) = (int(q0[1]), int(q0[2]), int(q0[3]))
        if not nx[l]:
            i = get_max(1, l - 1)
            v[l] = v[i]
            nx[l] = nx[i]
            nx[i] = l - 1
            update(l, l)
        if not nx[r + 1]:
            i = get_max(l, r)
            v[r + 1] = v[i]
            nx[r + 1] = nx[i]
            nx[i] = r
            update(r + 1, r + 1)
        i = l
        while i <= r:
            j = nx[i]
            add(i, j, u[v[i]])
            if i ^ l:
                update(i, 0)
            (nx[i], v[i]) = (0, 0)
            i = j + 1
        (nx[l], v[l]) = (r, c)
        add(l, r, -u[c])
    elif q0[0] == 'Add':
        (c, x) = (int(q0[1]), int(q0[2]))
        u[c] += x
    else:
        i = int(q0[1])
        c = v[get_max(1, i)]
        ans0 = get(i) + u[c]
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

    def val(self, it):
        """"""
        (pos, idx) = it
        return self._lists[pos][idx]

    def erase(self, it):
        """"""
        (pos, idx) = it
        self._delete(pos, idx)

    def begin(self):
        """"""
        return (0, 0)

    def end(self):
        """"""
        return (len(self._lists) - 1, len(self._lists[-1])) if self._lists else (0, 0)

    def prev(self, it):
        """"""
        (pos, idx) = it
        return (pos, idx - 1) if idx else (pos - 1, len(self._lists[pos - 1]) - 1)

    def next(self, it):
        """"""
        (pos, idx) = it
        return (pos, idx + 1) if pos + 1 == len(self._lists) or idx + 1 != len(self._lists[pos]) else (pos + 1, 0)

class FenwickTreeSum:

    def __init__(self, N):
        """"""
        self.tree = [0] * N

    def query(self, end):
        """"""
        x = 0
        while end:
            x += self.tree[end - 1]
            end &= end - 1
        return x

    def update(self, idx, x):
        """"""
        while idx < len(self.tree):
            self.tree[idx] += x
            idx |= idx + 1

def solve():
    (N, Q) = list(map(int, input().split()))
    starts = SortedList([0])
    colors = [1] + [0] * N

    def split(x):
        it = starts.prev(starts._loc_right(x))
        s = starts.val(it)
        if s == x:
            return
        starts.add(x)
        colors[x] = colors[s]
    add = [0] * (N + 1)
    fen = FenwickTreeSum(N + 1)

    def add_range(s, e, v):
        fen.update(s, v)
        fen.update(e + 1, -v)
    res = []
    for _ in range(Q):
        ts = input().decode().strip().split()
        if ts[0] == 'Color':
            (l, r, c) = (int(ts[1]) - 1, int(ts[2]), int(ts[3]))
            split(l)
            split(r)
            it = starts.prev(starts._loc_right(l))
            remove = []
            while starts.val(it) != r:
                s = starts.val(it)
                nit = starts.next(it)
                add_range(s, starts.val(nit) - 1, add[colors[s]] - add[c])
                it = nit
                remove.append(s)
            for s in remove:
                starts.remove(s)
            colors[l] = c
            starts.add(l)
        elif ts[0] == 'Add':
            (c, x) = (int(ts[1]), int(ts[2]))
            add[c] += x
        elif ts[0] == 'Query':
            x = int(ts[1]) - 1
            i = starts.bisect_right(x) - 1
            v = fen.query(x + 1) + add[colors[starts[i]]]
            res.append(v)
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    solve()