codeforcesRound#275(div2)D解题报告

#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();
}