首页 > 代码库 > Codeforces 482B Interesting Array 构造+线段树判可行
Codeforces 482B Interesting Array 构造+线段树判可行
题目链接:点击打开链接
题意:
构造一个n长的序列,m个限制:
每个限制[l, r] q
序列要满足 区间[l,r]的所有数 & 起来结果是q
思路:
直接构造,然后判可行就好了。。
#include <stdio.h> #include <cstring> #include <iostream> #include <map> template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef unsigned long long ull; #define L(x) tree[x].l #define R(x) tree[x].r #define Lson(x) (x<<1) #define Rson(x) (x<<1|1) #define V(x) tree[x].val const int N = 100005; int hehe; int haha; struct node{ int l, r, val; }tree[N<<2]; int a[N]; void push_up(int id){ V(id) = V(Lson(id)) & V(Rson(id)); } void build(int l, int r, int id){ L(id) = l ; R(id) = r; if(l == r){ V(id) = a[l]; return ; } int mid = (l+r)>>1; build(l, mid, Lson(id)); build(mid+1, r, Rson(id)); push_up(id); } int query(int l, int r, int id){ if(l == L(id) && R(id) == r){ return V(id); } int mid = (L(id) + R(id)) >> 1; if(mid < l) return query(l, r, Rson(id)); else if(r <= mid) return query(l, r, Lson(id)); else return query(l, mid, Lson(id)) & query(mid+1, r, Rson(id)); } int n, m; struct Q{ int l, r, q; }q[N]; int o[N][32], t[N][32]; void put(){ for(int i = 1; i <= n; i++) { pt(a[i]); i == n ? puts("") : putchar(' '); } } bool work(){ int now = 0; int b[35] = {0}; for(int i = 1; i <= n; i++) { for(int j = 0; j < 31; j++) if(o[i][j]) { now |= (1<<j); b[j]+=o[i][j]; } a[i] = now for(int j = 0; j < 31; j++) if(t[i][j]) { b[j]+=t[i][j]; if(b[j]==0) now &= ~(1<<j); } } build(1, n, 1); for(int i = 1; i <= m; i++) { if(query(q[i].l, q[i].r, 1) != q[i].q)return false; } return true; } bool input(){ memset(o, 0, sizeof o); memset(t, 0, sizeof t); for(int i = 1; i <= m; i++){ scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].q); for(int j = 0; j < 31; j++) if(q[i].q&(1<<j)) { o[q[i].l][j] ++; t[q[i].r][j] --; } } return true; } int main(){ while(cin>>n>>m){ input(); if(work()){ puts("YES"); put(); } else puts("NO"); } return 0; }
Codeforces 482B Interesting Array 构造+线段树判可行
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。