CodeforcesRound#275(Div.1)B（线段树+位运算）_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#275(Div.1)B（线段树+位运算）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2217字，纯文字阅读大概需要4分钟。
内容图文
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就能够成功构
造出来
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#275(Div.1)B（线段树+位运算）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#275(Div.1)B（线段树+位运算）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。