首页 > 代码库 > Codeforces 482B Interesting Array(线段树)
Codeforces 482B Interesting Array(线段树)
题目链接:Codeforces 482B Interesting Array
题目大意:给定一个长度为N的数组,现在有M个限制,每个限制有l,r,q,表示从a[l]~a[r]取且后的数一定为q,问是
否有满足的数列。
解题思路:线段树维护,每条限制等于是对l~r之间的数或上q(取且的性质,相应二进制位一定为1),那么处理完所有的
限制,在进行查询,查询对应每个l~r之间的数取且是否还等于q。所以用线段树维护取且和,修改为或操作。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int INF = (1<<30)-1;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], set[maxn << 2], val[maxn << 2];
inline void maintain (int u, int w) {
val[u] |= w;
set[u] |= w;
}
inline void pushup(int u) {
val[u] = val[lson(u)] & val[rson(u)];
}
inline void pushdown(int u) {
if (set[u]) {
maintain(lson(u), set[u]);
maintain(rson(u), set[u]);
set[u] = 0;
}
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
set[u] = val[u] = 0;
if (l == r)
return;
int mid = (lc[u] + rc[u]) >> 1;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int w) {
if (l <= lc[u] && rc[u] <= r) {
maintain(u, w);
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) >> 1;
if (l <= mid)
modify(lson(u), l, r, w);
if (r > mid)
modify(rson(u), l, r, w);
pushup(u);
}
int query(int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r)
return val[u];
pushdown(u);
int mid = (lc[u] + rc[u]) >> 1, ret = INF;
if (l <= mid)
ret &= query(lson(u), l, r);
if (r > mid)
ret &= query(rson(u), l, r);
pushup(u);
return ret;
}
int N, M, L[maxn], R[maxn], Q[maxn];
bool judge() {
for (int i = 0; i < M; i++)
if (query(1, L[i], R[i]) != Q[i])
return true;
printf("YES\n");
for (int i = 1; i <= N; i++)
printf("%d%c", query(1, i, i), i == N ? ‘\n‘ : ‘ ‘);
return false;
}
int main () {
scanf("%d%d", &N, &M);
build(1, 1, N);
for (int i = 0; i < M; i++) {
scanf("%d%d%d", &L[i], &R[i], &Q[i]);
modify(1, L[i], R[i], Q[i]);
}
if (judge())
printf("NO\n");
return 0;
}
Codeforces 482B Interesting Array(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。