codeforces Round #275(div2) D解題報告

codeforces Round #275(div2) D解題報告

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?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]?

If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.

Sample test(s) input

3 1
1 3 3

output

YES
3 3 3

input

3 2
1 3 3
1 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, n

using namespace std;

const int noth = (1<<30)-1;

int n, m;
int l[M_max], r[M_max], q[M_max], a[N_max];
int sum[N_max], tree[N_max*3];

void build(int v, int l, int r) {
	if (l == r) {
		tree[v] = a[l];
		return;
	}

	int ls = v<<1, rs = ls+1, mid = (l+r)>>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 < ql || l > qr)  return noth;

	if (ql <= l && r <= qr)  return tree[v];

	int ls = v<<1, rs = ls+1, mid = (l+r)>>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 <= m; i++)
		scanf("%d%d%d", &l[i], &r[i], &q[i]);

	for (int i = 0; i <= Maxbit; i++) {
		memset(sum, 0, sizeof(sum));

		for (int j = 1; j <= m; j++)
			if ((q[j] >> i) & 1) {
				sum[l[j]]++;
				sum[r[j]+1]--;
			}

		for (int j = 1; j <= n; j++) {
			sum[j] += sum[j-1];
			if (sum[j] > 0)  a[j] |= 1 << i;
		}
	}

	build(root);
}

void solve() {
	for (int i = 1; i <= m; i++)
		if (query(root, l[i], r[i]) != q[i]) {
			printf("NO\n");
			return;
		}

	printf("YES\n");
	for (int i = 1; i <= n; i++)  printf("%d ", a[i]);
	printf("\n");
}

int main() {
	init();
	solve();
}