Sanae and Giant Robot (Codeforces 1688F)
Tags: Others, dsu

Is it really?! The robot only existing in my imagination?! The Colossal Walking Robot?!!— Kochiya Sanae Sanae made a giant robot — Hisoutensoku, but something is wrong with it. To make matters worse, Sanae can not figure out how to stop it, and she is forced to fix it on-the-fly.The state of a robot can be represented by an array of integers of length $$$n$$$. Initially, the robot is at state $$$a$$$. She wishes to turn it into state $$$b$$$. As a great programmer, Sanae knows the art of copy-and-paste. In one operation, she can choose some segment from given segments, copy the segment from $$$b$$$ and paste it into the same place of the robot, replacing the original state there. However, she has to ensure that the sum of $$$a$$$ does not change after each copy operation in case the robot go haywire. Formally, Sanae can choose segment $$$[l,r]$$$ and assign $$$a_i = b_i$$$ ($$$l\le i\le r$$$) if $$$\sum\limits_{i=1}^n a_i$$$ does not change after the operation.Determine whether it is possible for Sanae to successfully turn the robot from the initial state $$$a$$$ to the desired state $$$b$$$ with any (possibly, zero) operations.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — the number of test cases. The descriptions of the test cases follow.The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n\leq 2\cdot 10^5$$$, $$$1 \leq m\leq 2\cdot 10^5$$$) — the length of $$$a$$$, $$$b$$$ and the number of segments.The second line contains $$$n$$$ intergers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial state $$$a$$$.The third line contains $$$n$$$ intergers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — the desired state $$$b$$$.Then $$$m$$$ lines follow, the $$$i$$$-th line contains two intergers $$$l_i,r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — the segments that can be copy-pasted by Sanae.It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

Output: For each test case, print "YES" (without quotes) if $$$a$$$ can be turned into $$$b$$$, or "NO" (without quotes) otherwise.You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Note: Test case 1:One possible way of turning $$$a$$$ to $$$b$$$:First, select $$$[1,3]$$$. After the operation, $$$a=[3,2,5,2,3]$$$.Then, select $$$[2,5]$$$. After the operation, $$$a=[3,2,5,4,1]=b$$$.Test case 2:It can be shown that it is impossible to turn $$$a$$$ into $$$b$$$. 

Sample Inputs:
2
5 2
1 5 4 2 3
3 2 5 4 1
1 3
2 5
5 2
1 5 4 2 3
3 2 4 5 1
1 2
2 4

Sample Outputs:
YES
NO

Solution (Python):
import os, 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')

class DisJoinUnion:

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

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

    def union(self, x, y):
        (fx, fy) = (self.find(x), self.find(y))
        if fx == fy:
            return
        self.parent[fy] = fx
        self.rank[fx] += self.rank[fy]
t = int(input())
for _ in range(t):
    (n, m) = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    sa = [0] * (n + 1)
    sb = [0] * (n + 1)
    for i in range(1, n + 1):
        sa[i] = sa[i - 1] + a[i - 1]
        sb[i] = sb[i - 1] + b[i - 1]
    dsu = DisJoinUnion(n + 2)
    l = [0] * m
    r = [0] * m
    deg = [2] * m
    g = [[] for _ in range(n + 1)]
    for i in range(m):
        (l[i], r[i]) = [int(x) for x in input().split()]
        l[i] -= 1
        g[l[i]].append(i)
        g[r[i]].append(i)

    def dfs(i):
        dsu.union(i + 1, i)
        for j in g[i]:
            deg[j] -= 1
            if deg[j] == 0:
                x = dsu.find(l[j])
                while x <= r[j]:
                    dfs(x)
                    x = dsu.find(x)
    for i in range(n + 1):
        if sa[i] == sb[i]:
            dfs(i)
    if dsu.find(0) == n + 1:
        print('YES')
    else:
        print('NO')

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 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):
        """"""
        if it == self.begin():
            raise ValueError('{0!r} already list begin'.format(it))
        (pos, idx) = it
        return (pos, idx - 1) if idx else (pos - 1, len(self._lists[pos - 1]) - 1)

    def next(self, it):
        """"""
        if it == self.end():
            raise ValueError('{0!r} already list end'.format(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)

def solve(N, M, A, B, segs):
    D = [0] * (N + 1)
    stack = [0]
    nonzero = SortedList()
    for (i, (a, b)) in enumerate(zip(A, B)):
        D[i + 1] = D[i] + a - b
        if D[i + 1] == 0:
            stack.append(i + 1)
        else:
            nonzero.add(i + 1)
    deg = [2] * M
    adj = [[] for _ in range(N + 1)]
    for (i, (l, r)) in enumerate(segs):
        adj[l - 1].append(i)
        adj[r].append(i)
    while stack:
        i = stack.pop()
        for j in adj[i]:
            deg[j] -= 1
            if deg[j] == 0:
                (l, r) = segs[j]
                rm = []
                k = nonzero.bisect_left(l)
                while k < len(nonzero) and nonzero[k] <= r:
                    rm.append(nonzero[k])
                    k += 1
                for v in rm:
                    nonzero.discard(v)
                    stack.append(v)
    return 'YES' if not nonzero else 'NO'

def main():
    T = int(input())
    for _ in range(T):
        (N, M) = list(map(int, input().split()))
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        segs = [list(map(int, input().split())) for _ in range(M)]
        out = solve(N, M, A, B, segs)
        print(out)
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
import bisect

class BIT_SortedSet:

    def __init__(self, A, compress=True, sort_flag=False):
        self.compress = compress
        self.N = len(A)
        self.log = 0
        while self.N >= 1 << self.log + 1:
            self.log += 1
        if compress:
            if sort_flag:
                self.A = A
            else:
                self.A = sorted(A)
            self.index_dic = {}
            for i in range(len(A)):
                self.index_dic[self.A[i]] = i
        else:
            self.A = A
        self.BIT = [0] * (self.N + 5)
        self.size = 0
        self.cnt = [0] * self.N

    def BIT_add(self, i, x):
        idx = i + 1
        while idx < self.N + 1:
            self.BIT[idx] += x
            idx += idx & -idx

    def BIT_query(self, i):
        res = 0
        idx = i + 1
        while idx:
            res += self.BIT[idx]
            idx -= idx & -idx
        return res

    def BIT_lower_left(self, w):
        if w <= 0 or w > self.size:
            return None
        x = 0
        k = 1 << self.log
        while k > 0:
            if x + k < self.N and self.BIT[x + k] < w:
                w -= self.BIT[x + k]
                x += k
            k //= 2
        return x

    def __contains__(self, x):
        if self.compress:
            x = self.index_dic[x]
        return self.cnt[x] >= 1

    def __len__(self):
        return self.size

    def add(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] == 1:
            return False
        self.BIT_add(x, 1)
        self.size += 1
        self.cnt[x] += 1
        return True

    def discard(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] > 0:
            self.BIT_add(x, -1)
            self.size -= 1
            self.cnt[x] -= 1
            return True
        return False

    def find_kth_val(self, k):
        res = self.BIT_lower_left(k + 1)
        if res == None:
            return None
        if self.compress:
            res = self.A[res]
        return res

    def __getitem__(self, x):
        if x < 0:
            x += self.size
        if x < 0 or x >= self.size:
            raise IndexError
        return self.find_kth_val(x)

    def index_right(self, x):
        if self.N == 0:
            return 0
        if x < self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = min(x, self.N - 1)
        return self.BIT_query(y)

    def index(self, x):
        if self.N == 0:
            return 0
        if x <= self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = x
        if y >= self.N:
            y = self.N - 1
        elif self.A[y] == x:
            y -= 1
        return self.BIT_query(y)

    def gt(self, x):
        return self.find_kth_val(self.index_right(x))

    def ge(self, x):
        return self.find_kth_val(self.index(x))

    def lt(self, x):
        return self.find_kth_val(self.index(x) - 1)

    def le(self, x):
        return self.find_kth_val(self.index_right(x) - 1)

    def __str__(self):
        return '{' + ', '.join(map(str, [self.find_kth_val(i) for i in range(self.size)])) + '}'

def solve():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = [a[i] - b[i] for i in range(n)]
    d = [0] * (n + 1)
    S = BIT_SortedSet(list(range(n + 1)))
    for i in range(1, n + 1):
        S.add(i)
    todo = [0]
    for i in range(n):
        d[i + 1] = d[i] + c[i]
        if d[i + 1] == 0:
            todo.append(i + 1)
            S.discard(i + 1)
    seg = [[] for i in range(n + 1)]
    for _ in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        seg[l].append(r)
        seg[r].append(l)
    while todo:
        x = todo.pop()
        for y in seg[x]:
            if d[y] == 0:
                (l, r) = (min(x, y), max(x, y))
                nxt = S.gt(l)
                while nxt != None and nxt < y:
                    d[nxt] = 0
                    S.discard(nxt)
                    todo.append(nxt)
                    nxt = S.gt(nxt)
    if len(S) == 0:
        print('Yes')
    else:
        print('No')
for _ in range(int(input())):
    solve()