Codeforces Round #275 (Div. 1)B（线段树+位运算）_html/css_WEB-ITnose

B. Interesting Array

time limit per test

memory limit per test

input

output

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.

算家云

高效、便捷的人工智能算力服务平台

37

查看详情

立即学习“前端免费学习笔记（深入）”；

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 test(s)

input

3 11 3 3

output

YES3 3 3

input

3 21 3 31 3 2

output

NO

题意：给出很多个区间，使得每个区间的值相与为qi，要求构造出n个数使得每个区间都满足

思路：比如第i个区间，如果里面所有的数相与要为qi，那么将这些数写成二进制以后qi为1的位要全为1，剩下的位至少有一个要为0

            那么我可以初始化n个数为0，先把所有位必须为1的构造出来，对于m个区间可以用线段树完成，只做懒操作，区间的值相或（先不向上更新）

            然后再从1到n扫一遍线段树，把每个位置的数都更新到位，然后再次对于m个区间，现在只做向上更新（区间的值相与），然后只要所有区间的值都等于qi就能够成功构

            造出来