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?) が含まれています。

出力

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

興味深い配列が存在しない場合は、単一行に「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 #include #define Maxbit 29#define M_max 123456#define N_max 123456#define root 1, 1, nusing 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();}