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

时间:2016-06-24 11:54:33 来源:互联网 作者: 神秘的大神 字体:

B. Interesting Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard 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?

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]?

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就能够成功构


造出来