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就能够成功构
造出来
查看更多关于CodeforcesRound#275(Div.1)B（线段树+位运算）_html/css_WEB-的详细内容...