Little Artem and Time Machine (Codeforces 669E)
Tags: Others, data structures

Little Artem has invented a time machine! He could go anywhere in time, but all his thoughts of course are with computer science. He wants to apply this time machine to a well-known data structure: multiset.Artem wants to create a basic multiset of integers. He wants these structure to support operations of three types:  Add integer to the multiset. Note that the difference between set and multiset is that multiset may store several instances of one integer.  Remove integer from the multiset. Only one instance of this integer is removed. Artem doesn't want to handle any exceptions, so he assumes that every time remove operation is called, that integer is presented in the multiset.  Count the number of instances of the given integer that are stored in the multiset. But what about time machine? Artem doesn't simply apply operations to the multiset one by one, he now travels to different moments of time and apply his operation there. Consider the following example.  First Artem adds integer 5 to the multiset at the 1-st moment of time.  Then Artem adds integer 3 to the multiset at the moment 5.  Then Artem asks how many 5 are there in the multiset at moment 6. The answer is 1.  Then Artem returns back in time and asks how many integers 3 are there in the set at moment 4. Since 3 was added only at moment 5, the number of integers 3 at moment 4 equals to 0.  Then Artem goes back in time again and removes 5 from the multiset at moment 3.  Finally Artyom asks at moment 7 how many integers 5 are there in the set. The result is 0, since we have removed 5 at the moment 3. Note that Artem dislikes exceptions so much that he assures that after each change he makes all delete operations are applied only to element that is present in the multiset. The answer to the query of the third type is computed at the moment Artem makes the corresponding query and are not affected in any way by future changes he makes.Help Artem implement time travellers multiset.

Input: The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of Artem's queries.Then follow n lines with queries descriptions. Each of them contains three integers ai, ti and xi (1 ≤ ai ≤ 3, 1 ≤ ti, xi ≤ 109) — type of the query, moment of time Artem travels to in order to execute this query and the value of the query itself, respectively. It's guaranteed that all moments of time are distinct and that after each operation is applied all operations of the first and second types are consistent.

Output: For each ask operation output the number of instances of integer being queried at the given moment of time.


Sample Inputs:
6
1 1 5
3 5 5
1 2 5
3 6 5
2 3 5
3 7 5

3
1 1 1
2 2 1
3 3 1

Sample Outputs:
1
2
1

0

Solution (Python):
from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
    return sys.stdin.readline().rstrip('\r\n')

def out(var):
    sys.stdout.write(str(var))

def inpu():
    return int(inp())

def lis():
    return list(map(int, inp().split()))

def stringlis():
    return list(map(str, inp().split()))

def sep():
    return map(int, inp().split())

def strsep():
    return map(str, inp().split())

def fsep():
    return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def update(bit, v, i, len1):
    while v < len1:
        bit[v] += i
        v += v & -v

def get(bit, v):
    ans = 0
    while v != 0:
        ans += bit[v]
        v -= v & -v
    return ans

def main():
    how_much_noob_I_am = 1
    for _ in range(how_much_noob_I_am):
        n = inpu()
        arr = [lis() for i in range(n)]
        d = defaultdict(list)
        c = defaultdict(list)
        for (i, j, k) in arr:
            d[k].append(j)
            c[k].append(j)
        bit = {i: [0] * (len(d[i]) + 1) for i in d}
        for i in c:
            c[i].sort()
        for i in range(n):
            arr[i][1] = bisect.bisect_right(c[arr[i][2]], arr[i][1])
        for (a, b, x) in arr:
            if a == 1:
                update(bit[x], b, 1, len(bit[x]))
            elif a == 2:
                update(bit[x], b, -1, len(bit[x]))
            else:
                print(get(bit[x], b))
if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree:

    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

def solve():
    n = int(input())
    data = []
    for i in range(n):
        line = input().split()
        data.append(list(map(int, line)))
    queries_dict = {}
    for row_idx in range(n):
        ai = data[row_idx][0]
        ti = data[row_idx][1]
        xi = data[row_idx][2]
        if xi not in queries_dict:
            queries_dict[xi] = [[(row_idx, ai, ti)], {}]
        else:
            queries_dict[xi][0].append((row_idx, ai, ti))
        if ti not in queries_dict[xi][1]:
            queries_dict[xi][1][ti] = None
    results = {}
    for xi in queries_dict:
        times = queries_dict[xi][1]
        queries = queries_dict[xi][0]
        unique_times = sorted(times.keys())
        for (i, time) in enumerate(unique_times):
            times[time] = i + 1
        bit_ = BinaryIndexedTree(len(unique_times))
        for (row_idx, ai, ti) in queries:
            time_idx = times[ti]
            if ai == 1:
                bit_.update(time_idx, 1)
            elif ai == 2:
                bit_.update(time_idx, -1)
            elif ai == 3:
                results[row_idx] = bit_.prefix_sum(time_idx)
    counts = [str(results[key]) for key in sorted(results.keys())]
    if results:
        print('\n'.join(counts))
solve()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
new = lambda xx: (xx | xx - 1) + 1

def buildBIT(bit, n):
    for i in range(1, n + 1):
        x = new(i)
        if x <= n:
            bit[x] += bit[i]

def pointUpdate(bit, point, n, diff):
    while point <= n:
        bit[point] += diff
        point = new(point)

def calculatePrefix(bit, point):
    su = 0
    while point:
        su += bit[point]
        point &= point - 1
    return su

def rangeQuery(bit, start, stop):
    return calculatePrefix(bit, stop) - calculatePrefix(bit, start - 1)

def compressCoordinate(lst):
    return {i: ind + 1 for (ind, i) in enumerate(sorted(set(lst)))}

def main():
    from collections import defaultdict
    n = int(input())
    dct = defaultdict(list)
    oper = [list(map(int, input().split())) for _ in range(n)]
    for (a, t, x) in oper:
        dct[x].append(t)
    new = {i: compressCoordinate(dct[i]) for i in dct}
    for i in range(n):
        oper[i][1] = new[oper[i][2]][oper[i][1]]
    bit = {i: [0] * (len(dct[i]) + 1) for i in dct}
    for (a, t, x) in oper:
        if a == 1:
            pointUpdate(bit[x], t, len(bit[x]) - 1, 1)
        elif a == 2:
            pointUpdate(bit[x], t, len(bit[x]) - 1, -1)
        else:
            print(calculatePrefix(bit[x], t))
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()