Interesting Array (Codeforces 482B)
Tags: Others, trees

We'll call an array of n non-negative integers a[1], a[2], ..., a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value  should be equal to qi. Your task is to find any interesting array of n elements or state that such array doesn't exist.Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

Input: The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.

Output: If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print n integers a[1], a[2], ..., a[n] (0 ≤ a[i] < 230) decribing the interesting array. If there are multiple answers, print any of them.If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.


Sample Inputs:
3 1
1 3 3

3 2
1 3 3
1 3 2

Sample Outputs:
YES
3 3 3

NO

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = []
for _ in range(m):
    (l, r, q) = map(int, input().split())
    l -= 1
    r -= 1
    a.append((l, r, q))
res = [0] * n
bad = False
for i in range(30):
    events = [0] * (n + 1)
    for (l, r, q) in a:
        if q & 1 << i:
            events[l] += 1
            events[r + 1] -= 1
    c = 0
    for j in range(n):
        c += events[j]
        if c > 0:
            res[j] |= 1 << i
    s = [0] * (n + 1)
    for j in range(n):
        s[j + 1] = s[j] + (res[j] >> i & 1)
    for (l, r, q) in a:
        if q & 1 << i == 0:
            if s[r + 1] - s[l] == r - l + 1:
                bad = True
                break
if bad:
    print('NO')
else:
    print('YES')
    print(*res)

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

def funcand(a, b):
    return a & b

class SegmentTree:

    def __init__(self, data, default=(1 << 31) - 1, func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

def f(n, q):
    a = [0] * n
    for bit in range(30):
        s = [0] * (n + 1)
        for (l, r, nm) in q:
            if nm >> bit & 1:
                s[l] += 1
                s[r] -= 1
        for i in range(n):
            if i > 0:
                s[i] += s[i - 1]
            if s[i] > 0:
                a[i] |= 1 << bit
    st = SegmentTree(a, func=funcand, default=(1 << 31) - 1)
    for (l, r, nm) in q:
        if st.query(l, r) != nm:
            return 'NO'
    print('YES')
    print(*a)
    return ''
q = []
(n, m) = map(int, input().strip().split())
for _ in range(m):
    (l, r, nm) = map(int, input().strip().split())
    q.append((l - 1, r, nm))
print(f(n, q))

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

class Dual_Segment_Tree:

    def __init__(self, N, f_act, e_act, operate, lst):
        self.N = N
        self.f_act = f_act
        self.e_act = e_act
        self.operate = operate
        self.lst = [None] * self.N
        for (i, x) in enumerate(lst):
            self.lst[i] = x
        self.segment_tree_act = [self.e_act] * (self.N + self.N)

    def __getitem__(self, i):
        if type(i) is int:
            if -self.N <= i < 0:
                i += self.N * 2
            elif 0 <= i < self.N:
                i += self.N
            else:
                raise IndexError('list index out of range')
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None or a < -self.N:
                a = 0
            elif self.N <= a:
                a = self.N
            elif a < 0:
                a += self.N
            if b == None or self.N <= b:
                b = self.N
            elif b < -self.N:
                b = 0
            elif b < 0:
                b += self.N
            return self.lst[slice(a, b, c)]

    def Operate_At(self, i):
        return self.operate(self.lst[i - self.N], self.segment_tree_act[i])

    def Propagate_At(self, i):
        self.segment_tree_act[i << 1] = self.f_act(self.segment_tree_act[i << 1], self.segment_tree_act[i])
        self.segment_tree_act[i << 1 | 1] = self.f_act(self.segment_tree_act[i << 1 | 1], self.segment_tree_act[i])
        self.segment_tree_act[i] = self.e_act

    def Propagate_Above(self, i):
        H = i.bit_length() - 1
        for h in range(H, 0, -1):
            self.Propagate_At(i >> h)

    def Operate_Range(self, a, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L < R:
            if L & 1:
                self.segment_tree_act[L] = self.f_act(self.segment_tree_act[L], a)
                L += 1
            if R & 1:
                R -= 1
                self.segment_tree_act[R] = self.f_act(self.segment_tree_act[R], a)
            L >>= 1
            R >>= 1

    def Update(self):
        for i in range(1, self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i] = self.e_act

    def __str__(self):
        import copy
        segment_tree_act = copy.deepcopy(self.segment_tree_act)
        for i in range(1, self.N):
            segment_tree_act[i << 1] = self.f_act(segment_tree_act[i << 1], segment_tree_act[i])
            segment_tree_act[i << 1 | 1] = self.f_act(segment_tree_act[i << 1 | 1], segment_tree_act[i])
            segment_tree_act[i] = self.e_act
            segment_tree_act[i] = self.e_act
        return '[' + ', '.join(map(str, [self.operate(x, a) for (x, a) in zip(self.lst, segment_tree_act[self.N:])])) + ']'

class Segment_Tree:

    def __init__(self, N, f, e, lst=None):
        self.f = f
        self.e = e
        self.N = N
        if lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, l=None, f=None):
        if l == self.N:
            return self.N
        if l == None:
            l = 0
        if f(self.Fold(l, self.N)):
            return self.N
        l += self.N
        v = self.e
        while True:
            while l % 2 == 0:
                l >>= 1
            vv = self.f(v, self.segment_tree[l])
            if f(vv):
                v = vv
                l += 1
                if 2 * self.N == l << self.N.bit_length() - l.bit_length() + 1:
                    return self.N
            else:
                while l < self.N:
                    l <<= 1
                    vv = self.f(v, self.segment_tree[l])
                    if f(vv):
                        v = vv
                        l += 1
                return l - self.N

    def Bisect_Left(self, r=None, f=None):
        if r == 0:
            return 0
        if r == None:
            r = self.N
        if f(self.Fold(0, r)):
            return 0
        r += self.N
        v = self.e
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            vv = self.f(self.segment_tree[r], v)
            if f(vv):
                v = vv
                if 2 * self.N == r << self.N.bit_length() - r.bit_length() + 1:
                    return 0
            else:
                while r < self.N:
                    r = 2 * r + 1
                    vv = self.f(self.segment_tree[r], v)
                    if f(vv):
                        v = vv
                        r -= 1
                return r + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'
(N, M) = map(int, readline().split())
DST = Dual_Segment_Tree(N, lambda a, b: a | b, 0, lambda x, a: x | a, [0] * N)
query = []
for _ in range(M):
    (l, r, q) = map(int, readline().split())
    l -= 1
    DST.Operate_Range(q, l, r)
    query.append((l, r, q))
e = (1 << 32) - 1
ans_lst = [DST[i] for i in range(N)]
ST = Segment_Tree(N, lambda x, y: x & y, e, ans_lst)
for (l, r, q) in query:
    if ST.Fold(l, r) != q:
        print('NO')
        exit()
print('YES')
print(*ans_lst)