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?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 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就能够成功构
造出来
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/3093637.html
