搜索
首页web前端html教程codeforces Round #275(div2) D解题报告_html/css_WEB-ITnose

D. 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

题目大意:

假设有n个非负数,现在有m个限制,a[l] & a[l+1] & a[l+2] ... & a[r] = q。要求根据上述的限制,输出符合要求的1~n个数,如若不能则输出“NO”。

解法:

       我们先挖掘题意,弄清楚题目给的已知条件和要我们输出什么。

       a[l] & a[l+1] & a[l+2] ... & a[r] = q,这是每个限制的基本形式,由“&”我们可以得知,如若q中的某一个bit是1的话,则要求a[l]~a[r]中的那个bit位都为1。这个条件看似是限制,现在通过转化,似乎可以成为我们的已知条件,即每一个a[i]中的必须要为1的bit。

       通过上述可知,我们得到每个a[i]的基本值,然后每一个限制是一个区间,很容易就想到了线段树,对每一条限制进行查询,看是否冲突,如若冲突则为"NO“,如若不冲突,则就按照a[i]的必须值来输出即可。

代码:

#include <cstdio>#include <cstring>#define Maxbit 29#define M_max 123456#define N_max 123456#define root 1, 1, nusing namespace std;const int noth = (1>1;	build(ls, l, mid);	build(rs, mid+1, r);	tree[v] = tree[ls] & tree[rs];}int query(int v, int l, int r, int ql, int qr) {	if (r  qr)  return noth;	if (ql >1;	return query(ls, l, mid, ql, qr) & query(rs, mid+1, r, ql, qr);}void init() {	scanf("%d%d", &n, &m);	for (int i = 1; i > i) & 1) {				sum[l[j]]++;				sum[r[j]+1]--;			}		for (int j = 1; j  0)  a[j] |= 1   <p></p> </cstring></cstdio>
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
&gt; gt;的目的是什么 元素?&gt; gt;的目的是什么 元素?Mar 21, 2025 pm 12:34 PM

本文讨论了HTML&lt; Progress&gt;元素,其目的,样式和与&lt; meter&gt;元素。主要重点是使用&lt; progress&gt;为了完成任务和LT;仪表&gt;对于stati

&lt; datalist&gt;的目的是什么。 元素?&lt; datalist&gt;的目的是什么。 元素?Mar 21, 2025 pm 12:33 PM

本文讨论了html&lt; datalist&gt;元素,通过提供自动完整建议,改善用户体验并减少错误来增强表格。Character计数:159

&lt; meter&gt;的目的是什么。 元素?&lt; meter&gt;的目的是什么。 元素?Mar 21, 2025 pm 12:35 PM

本文讨论了HTML&lt; meter&gt;元素,用于在一个范围内显示标量或分数值及其在Web开发中的常见应用。它区分了&lt; meter&gt;从&lt; progress&gt;和前

HTML5中跨浏览器兼容性的最佳实践是什么?HTML5中跨浏览器兼容性的最佳实践是什么?Mar 17, 2025 pm 12:20 PM

文章讨论了确保HTML5跨浏览器兼容性的最佳实践,重点是特征检测,进行性增强和测试方法。

视口元标签是什么?为什么对响应式设计很重要?视口元标签是什么?为什么对响应式设计很重要?Mar 20, 2025 pm 05:56 PM

本文讨论了视口元标签,这对于移动设备上的响应式Web设计至关重要。它解释了如何正确使用确保最佳的内容缩放和用户交互,而滥用可能会导致设计和可访问性问题。

我如何使用html5&lt; time&gt; 元素以语义表示日期和时间?我如何使用html5&lt; time&gt; 元素以语义表示日期和时间?Mar 12, 2025 pm 04:05 PM

本文解释了HTML5&lt; time&gt;语义日期/时间表示的元素。 它强调了DateTime属性对机器可读性(ISO 8601格式)的重要性,并在人类可读文本旁边,增强Accessibilit

如何使用HTML5表单验证属性来验证用户输入?如何使用HTML5表单验证属性来验证用户输入?Mar 17, 2025 pm 12:27 PM

本文讨论了使用HTML5表单验证属性,例如必需的,图案,最小,最大和长度限制,以直接在浏览器中验证用户输入。

&lt; iframe&gt;的目的是什么。 标签?使用时的安全考虑是什么?&lt; iframe&gt;的目的是什么。 标签?使用时的安全考虑是什么?Mar 20, 2025 pm 06:05 PM

本文讨论了&lt; iframe&gt;将外部内容嵌入网页,其常见用途,安全风险以及诸如对象标签和API等替代方案的目的。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境