New Year Domino (Codeforces 500E)
Tags: DP, dsu

Celebrating the new year, many people post videos of falling dominoes; Here's a list of them: https://www.youtube.com/results?search_query=New+Years+Dominos User ainta, who lives in a 2D world, is going to post a video as well.There are n dominoes on a 2D Cartesian plane. i-th domino (1 ≤ i ≤ n) can be represented as a line segment which is parallel to the y-axis and whose length is li. The lower point of the domino is on the x-axis. Let's denote the x-coordinate of the i-th domino as pi. Dominoes are placed one after another, so p1 < p2 < ... < pn - 1 < pn holds.User ainta wants to take a video of falling dominoes. To make dominoes fall, he can push a single domino to the right. Then, the domino will fall down drawing a circle-shaped orbit until the line segment totally overlaps with the x-axis.   Also, if the s-th domino touches the t-th domino while falling down, the t-th domino will also fall down towards the right, following the same procedure above. Domino s touches domino t if and only if the segment representing s and t intersects.   See the picture above. If he pushes the leftmost domino to the right, it falls down, touching dominoes (A), (B) and (C). As a result, dominoes (A), (B), (C) will also fall towards the right. However, domino (D) won't be affected by pushing the leftmost domino, but eventually it will fall because it is touched by domino (C) for the first time.  The picture above is an example of falling dominoes. Each red circle denotes a touch of two dominoes.User ainta has q plans of posting the video. j-th of them starts with pushing the xj-th domino, and lasts until the yj-th domino falls. But sometimes, it could be impossible to achieve such plan, so he has to lengthen some dominoes. It costs one dollar to increase the length of a single domino by 1. User ainta wants to know, for each plan, the minimum cost needed to achieve it. Plans are processed independently, i. e. if domino's length is increased in some plan, it doesn't affect its length in other plans. Set of dominos that will fall except xj-th domino and yj-th domino doesn't matter, but the initial push should be on domino xj.

Input: The first line contains an integer n (2 ≤ n ≤ 2 × 105)— the number of dominoes.Next n lines describe the dominoes. The i-th line (1 ≤ i ≤ n) contains two space-separated integers pi, li (1 ≤ pi, li ≤ 109)— the x-coordinate and the length of the i-th domino. It is guaranteed that p1 < p2 < ... < pn - 1 < pn.The next line contains an integer q (1 ≤ q ≤ 2 × 105) — the number of plans.Next q lines describe the plans. The j-th line (1 ≤ j ≤ q) contains two space-separated integers xj, yj (1 ≤ xj < yj ≤ n). It means the j-th plan is, to push the xj-th domino, and shoot a video until the yj-th domino falls.

Output: For each plan, print a line containing the minimum cost needed to achieve it. If no cost is needed, print 0.

Note: Consider the example. The dominoes are set like the picture below.  Let's take a look at the 4th plan. To make the 6th domino fall by pushing the 2nd domino, the length of the 3rd domino (whose x-coordinate is 4) should be increased by 1, and the 5th domino (whose x-coordinate is 9) should be increased by 1 (other option is to increase 4th domino instead of 5th also by 1). Then, the dominoes will fall like in the picture below. Each cross denotes a touch between two dominoes.           

Sample Inputs:
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6

Sample Outputs:
0
1
1
2

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

class Fenwick:
    size = 0
    bit = []

    def __init__(self, n):
        for i in range(n + 1):
            self.bit.append(0)
        self.size = n

    def update(self, pos, val):
        u = pos
        while u <= self.size:
            self.bit[u] += val
            u += u & -u

    def get(self, pos):
        (res, u) = (0, pos)
        while u > 0:
            res += self.bit[u]
            u -= u & -u
        return res

def main():
    n = int(input())
    pos = [-1]
    hgt = [-1]
    for i in range(1, n + 1):
        (p, h) = [int(x) for x in input().split()]
        pos.append(p)
        hgt.append(h)
    q = int(input())
    ans = [0 for x in range(q)]
    query = [[] for x in range(n + 1)]
    for i in range(1, q + 1):
        (l, r) = [int(x) for x in input().split()]
        query[l].append((r, i))
    stack = []
    tree = Fenwick(n)
    for i in range(n, 0, -1):
        while len(stack) > 0:
            top = stack[-1]
            if pos[top] > pos[i] + hgt[i]:
                need = pos[top] - pos[i] - hgt[i]
                tree.update(top, min(0, need - tree.get(top) + tree.get(top - 1)))
                break
            tree.update(top, -tree.get(top) + tree.get(top - 1))
            stack.pop()
        stack.append(i)
        for j in query[i]:
            ans[j[1] - 1] = tree.get(j[0])
        tree.update(i, pos[i] - pos[i - 1])
    print('\n'.join(map(str, ans)))
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')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import io, os, sys
if 'PyPy' in sys.version:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    def strput():
        return input().decode()
else:
    input = sys.stdin.readline

    def strput():
        return input()

class Fenwick:
    size = 0
    bit = []

    def __init__(self, n):
        for i in range(n + 1):
            self.bit.append(0)
        self.size = n

    def update(self, pos, val):
        u = pos
        while u <= self.size:
            self.bit[u] += val
            u += u & -u

    def get(self, pos):
        (res, u) = (0, pos)
        while u > 0:
            res += self.bit[u]
            u -= u & -u
        return res

def main():
    n = int(input())
    pos = [-1]
    hgt = [-1]
    for i in range(1, n + 1):
        (p, h) = [int(x) for x in input().split()]
        pos.append(p)
        hgt.append(h)
    q = int(input())
    ans = [0 for x in range(q)]
    query = [[] for x in range(n + 1)]
    for i in range(1, q + 1):
        (l, r) = [int(x) for x in input().split()]
        query[l].append((r, i))
    stack = []
    tree = Fenwick(n)
    for i in range(n, 0, -1):
        while len(stack) > 0:
            top = stack[-1]
            if pos[top] > pos[i] + hgt[i]:
                need = pos[top] - pos[i] - hgt[i]
                tree.update(top, min(0, need - tree.get(top) + tree.get(top - 1)))
                break
            tree.update(top, -tree.get(top) + tree.get(top - 1))
            stack.pop()
        stack.append(i)
        for j in query[i]:
            ans[j[1] - 1] = tree.get(j[0])
        tree.update(i, pos[i] - pos[i - 1])
    print('\n'.join(map(str, ans)))
if __name__ == '__main__':
    main()

Solution (Python):
""""""
import os
import sys
from io import BytesIO, IOBase
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')

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def A(n):
    return [0] * n

def AI(n, x):
    return [x] * n

def A2(n, m):
    return [[0] * m for i in range(n)]

def G(n):
    return [[] for i in range(n)]

def GP(it):
    return [[ch, len(list(g))] for (ch, g) in groupby(it)]
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
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    fact(x, mod)
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa.reverse()

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def floorsum(a, b, c, n):
    if a == 0:
        return b // c * (n + 1)
    if a >= c or b >= c:
        return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
    m = (a * n + b) // c
    return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
    return n & -n

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class ST:

    def __init__(self, arr):
        n = len(arr)
        mx = n.bit_length()
        self.st = [[0] * mx for i in range(n)]
        for i in range(n):
            self.st[i][0] = arr[i]
        for j in range(1, mx):
            for i in range(n - (1 << j) + 1):
                self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

    def query(self, l, r):
        if l > r:
            return -inf
        s = (r + 1 - l).bit_length() - 1
        return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] > self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return flag

def dij(s, graph):
    d = {}
    d[s] = 0
    heap = [(0, s)]
    seen = set()
    while heap:
        (dis, u) = heappop(heap)
        if u in seen:
            continue
        seen.add(u)
        for (v, w) in graph[u]:
            if v not in d or d[v] > d[u] + w:
                d[v] = d[u] + w
                heappush(heap, (d[v], v))
    return d

def bell(s, g):
    dis = AI(n, inf)
    dis[s] = 0
    for i in range(n - 1):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
    change = A(n)
    for i in range(n):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                change[v] = 1
    return dis

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

def lis(nums):
    res = []
    for k in nums:
        i = bisect.bisect_left(res, k)
        if i == len(res):
            res.append(k)
        else:
            res[i] = k
    return len(res)

def RP(nums):
    n = len(nums)
    s = set(nums)
    d = {}
    for (i, k) in enumerate(sorted(s), 1):
        d[k] = i
    bi = BIT([0] * (len(s) + 1))
    ans = 0
    for i in range(n - 1, -1, -1):
        ans += bi.query(d[nums[i]] - 1)
        bi.update(d[nums[i]], 1)
    return ans

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def nb(i, j, n, m):
    for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < n and 0 <= nj < m:
            yield (ni, nj)

def topo(n):
    q = deque()
    res = []
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            res.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r, p):
    for ch in g[r]:
        if ch != p:
            yield gdfs(ch, r)
    yield None

class SMT:

    def __init__(self, n, query_fn, I):
        self.h = 1
        while 1 << self.h < n:
            self.h += 1
        self.n = 1 << self.h
        self.qf = query_fn
        self.tree = [I] * (self.n << 1)
        self.lazy = [0] * self.n

    def build(self, v):
        for k in range(len(v)):
            self.tree[k + self.n] = v[k]
        for k in range(self.n - 1, 0, -1):
            self.tree[k] = self.qf(self.tree[2 * k], self.tree[2 * k + 1])

    def apply(self, x, val):
        self.tree[x] = val
        if x < self.n:
            self.lazy[x] = 1

    def pushup(self, x):
        self.tree[x] = self.qf(self.tree[2 * x], self.tree[2 * x + 1])

    def push(self, x):
        if self.lazy[x]:
            self.apply(x * 2, 0)
            self.apply(x * 2 + 1, 0)
            self.lazy[x] = 0

    def set(self, p, x):
        p += self.n
        for i in range(self.h, 0, -1):
            self.push(p >> i)
        self.tree[p] = x
        for i in range(1, self.h + 1):
            self.pushup(p >> i)

    def get(self, p):
        p += self.n
        for i in range(self.h, 0, -1):
            self.push(p >> i)
        return self.tree[p]

    def update(self, l, r, h):
        l += self.n
        r += self.n
        l0 = l
        r0 = r
        for i in range(self.h, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r + 1 >> i << i != r + 1:
                self.push(r >> i)
        while l <= r:
            if l & 1:
                self.apply(l, h)
                l += 1
            if not r & 1:
                self.apply(r, h)
                r -= 1
            l >>= 1
            r >>= 1
        for i in range(1, self.h + 1):
            if l0 >> i << i != l0:
                self.pushup(l0 >> i)
            if r0 + 1 >> i << i != r0 + 1:
                self.pushup(r0 >> i)

    def query(self, l, r):
        l += self.n
        r += self.n
        for i in range(self.h, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r + 1 >> i << i != r + 1:
                self.push(r >> i)
        ans = 0
        while l <= r:
            if l & 1:
                ans = self.qf(ans, self.tree[l])
                l += 1
            if not r & 1:
                ans = self.qf(ans, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return ans

def add(x, y):
    return x + y
t = 1
for i in range(t):
    n = N()
    s = set()
    x = A(n)
    y = A(n)
    for i in range(n):
        (p, l) = RL()
        x[i] = p
        y[i] = p + l
        s.add(p)
        s.add(y[i])
    s = sorted(s)
    d = {x: i for (i, x) in enumerate(s)}
    k = len(s) - 1
    arr = [s[i] - s[i - 1] for i in range(1, k + 1)]
    smt = SMT(k, add, 0)
    smt.build(arr)
    g = G(n)
    q = N()
    ans = A(q)
    for i in range(q):
        (a, b) = RL()
        a -= 1
        b -= 1
        g[a].append((i, b))
    for i in range(n - 1, -1, -1):
        l = d[x[i]]
        r = d[y[i]]
        smt.update(l, r - 1, 0)
        for (j, cur) in g[i]:
            cur = d[x[cur]]
            ans[j] = smt.query(l, cur - 1)
    for x in ans:
        print(x)
''