codeforces Round #275(div2) D問題解決レポート_html/css_WEB-ITnose

D. 興味深い配列

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

m個の制約を満たす場合、n個の非負の整数a[1]、?a[2]、?...、?a[n]の配列を興味深いと呼びます。 m 個の制約の i 番目は、3 つの整数 li、ri、qi (1?≤?li?≤?ri?≤?n) で構成されます。これは、値が qi に等しい必要があることを意味します。

あなたのタスクは、興味深いものを見つけることです。 n 要素の配列、またはそのような配列が存在しないことを示します。

式 x&y は、数値 x と y のビット単位の AND を意味します。プログラミング言語 C++、Java、Python では、この操作は Pascal では "&" として表されます。

入力

最初の行には 2 つの整数 n, m (1?≤?n?≤?105, 1?≤?m?≤?105)? が含まれています。配列内の要素の数と制限の数です。

次の m 行には、それぞれ 3 つの整数 li、ri、qi (1?≤?li?≤?ri?≤?n, 0?≤?qi?) が含まれています。 230) i 番目の制限を記述します。

出力

興味深い配列が存在する場合、最初の行に "YES" (引用符なし) を出力し、2 行目に n 整数 a[1] を出力します。 、?a[2]、?...、?a[n] (0?≤?a[i]?230) は、興味深い配列を記述します。複数の回答がある場合は、いずれかを出力します。

興味深い配列が存在しない場合は、単一行に「NO」(引用符なし) を出力します。

サンプル テスト

入力

3 11 3 3

出力

YES3 3 3

入力

3 21 3 31 3 2

出力

NO

题目大意：

假设有n个非负数，现在有m制限，a[l] & a[l+1] & a[l+2] ... & a[r] = q。 要求 前述の制限に従って、「いいえ」を出力できない場合は、要求に対応する 1 ～ n の数が出力されます。

解法：

私は先んじて探求し、明確な目给の既知条件と要我们出力物。

a[l] & a[l+1] & a[l+2] 。 .. & a[r] = q、これはそれぞれの制限の基本的な形式です、「&」によって知ることができます、例えば若qの中の特定のビットが 1 であるということ、a[l]~a[r] が必要ですこの条件は制限されているようで、変換により既知の条件、つまり各 a[i] のビットが必ず 1 になる可能性があります。 ，私たちは各 a[i] の基本値を取得しました、その後、各制限は 1 つの区域です、簡単に線区に到達できます、各条の制限を実行します、突発かどうかを確認します、突発が "NO" の場合、そうでない場合

代コード：

#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  </cstring></cstdio>