Sanae and Giant Robot (Codeforces 1687C)
Tags: Greedy, 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 io, os
import bisect
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n
        self.maxd = len(bin(n)) - 3

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

    def search(self, target):
        accunum = 0
        accuindex = 0
        for i in range(self.maxd, -1, -1):
            d = 1 << i
            if accuindex + d > self.n:
                continue
            if accunum + self.cul[accuindex + d - 1] <= target:
                accunum += self.cul[accuindex + d - 1]
                accuindex += d
        return accuindex

def main(t):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    accu = [0] * (n + 1)
    for i in range(n):
        accu[i] = accu[i - 1] + a[i] - b[i]
    rest = [2] * m
    corseg = [[] for _ in range(n + 1)]
    segments = []
    for j in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        segments.append([l, r])
        corseg[l - 1].append(j)
        corseg[r].append(j)
    nonzero = fenwick(n)
    queue = deque()
    for i in range(-1, n):
        if accu[i] == 0:
            while corseg[i]:
                index = corseg[i].pop()
                rest[index] -= 1
                if rest[index] == 0:
                    queue.append(index)
        else:
            nonzero.update(i, 1)
    while queue:
        index = queue.popleft()
        (left, right) = (segments[index][0], segments[index][1])
        leftnum = nonzero.getaccu(left - 1)
        rightnum = nonzero.getaccu(right)
        num = rightnum - leftnum
        for _ in range(rightnum - leftnum):
            loc = nonzero.search(leftnum)
            while corseg[loc]:
                nextindex = corseg[loc].pop()
                rest[nextindex] -= 1
                if rest[nextindex] == 0:
                    queue.append(nextindex)
            nonzero.update(loc, -1)
    if nonzero.getaccu(n - 1) > 0:
        print('NO')
    else:
        print('YES')
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
input = sys.stdin.readline

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.max_ = [i for i in range(n)]
        self.group = n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.group -= 1
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        if self.max_[y] > self.max_[x]:
            self.max_[x] = self.max_[y]

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return self.group

    def all_group_members(self):
        dic = {r: [] for r in self.roots()}
        for i in range(self.n):
            dic[self.find(i)].append(i)
        return dic

    def __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def solve():
    (n, m) = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    cuma = [0]
    cumb = [0]
    for a in A:
        cuma.append(cuma[-1] + a)
    for b in B:
        cumb.append(cumb[-1] + b)
    if cuma[-1] != cumb[-1]:
        for _ in range(m):
            input()
        print('NO')
        return
    lst = [[] for _ in range(n + 1)]
    cnt = [0] * m
    L = []
    R = []
    for i in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        lst[l].append(i)
        lst[r].append(i)
        L.append(l)
        R.append(r)
    UF = UnionFind(n + 1)
    stack = []
    tf = [False] * (n + 1)
    for i in range(n + 1):
        if cuma[i] == cumb[i]:
            tf[i] = True
            if i != n:
                UF.union(i, i + 1)
            for j in lst[i]:
                cnt[j] += 1
                if cnt[j] == 2:
                    stack.append(j)
    while stack:
        i = stack.pop()
        (l, r) = (L[i], R[i])
        while 1:
            l = UF.max_[UF.find(l)]
            if l >= r or l >= n:
                break
            UF.union(l, l + 1)
            tf[l] = True
            for j in lst[l]:
                cnt[j] += 1
                if cnt[j] == 2:
                    stack.append(j)
    if all((t for t in tf)):
        print('YES')
    else:
        print('NO')
for _ in range(int(input())):
    solve()

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')