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
题目大意：
假设有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 #include #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
查看更多关于codeforcesRound#275(div2)D解题报告_html/css_WEB-ITnose的详细内容...