參考了Yoangh大牛的博客

鏈接：http://blog.csdn.net/y990041769/article/details/40590953

題意：構建一個有n個元素的序列，滿足題中給出的m條約束，即數列要滿足第Li個數字到第Ri個數字的&等于Qi，如有滿足的序列，輸出YES，否則輸出NO。

思路：如果某個位置處于不同的區間交內，那么這個位置的數字一定要等于那些區間的Qi的或，這樣才能把每一位的1保存下來，處理的時候每讀入一條約束，用線段樹去更新，讀完數據判斷是否所有區間都滿足約束，若滿足，則在線段樹內從上至下的更新答案。

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream>using namespace std;const int N=1e5+2; int ans[N]; int ii;struct C {int l,r,q; } c[100005];struct Node {int l,r,s; } tree[N*4];void build(int l,int r,int root) {tree[root].l=l;tree[root].r=r;tree[root].s=0;if(l==r)return ;int m=(l+r)>>1;build(l,m,root<<1);build(m+1,r,root<<1|1); }void update(int l,int r,int c,int root) {if(tree[root].l==l&&tree[root].r==r){tree[root].s=tree[root].s|c;return ;}int m=(tree[root].l+tree[root].r)>>1;if(r<=m)update(l,r,c,root<<1);else if(l>m)update(l,r,c,root<<1|1);else{update(l,m,c,root<<1);update(m+1,r,c,root<<1|1);} }int query(int l,int r,int root) {if(tree[root].l==l&&tree[root].r==r)return tree[root].s;int m=(tree[root].l+tree[root].r)>>1;if(r<=m)return query(l,r,root<<1);else if(l>m)return query(l,r,root<<1|1);elsereturn query(l,m,root<<1)&query(m+1,r,root<<1|1); }void solve(int root) {if(root!=1)tree[root].s|=tree[root>>1].s;if(tree[root].l==tree[root].r){ans[ii]=tree[root].s;ii++;return ;}solve(root<<1);solve(root<<1|1); }int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){build(1,n,1);for(int i=1; i<=m; i++){scanf("%d%d%d",&c[i].l,&c[i].r,&c[i].q);update(c[i].l,c[i].r,c[i].q,1);}int flag=1;for(int i=1; i<=m; i++){if(query(c[i].l,c[i].r,1)!=c[i].q){flag=0;break;}}if(flag){printf("YES\n");ii=1;solve(1);for(int i=1; i<ii; i++){if(i==1)printf("%d",ans[i]);elseprintf(" %d",ans[i]);}printf("\n");}elseprintf("NO\n");}return 0; }

總結

以上是生活随笔為你收集整理的CF_275_DIV2_D_Interesting Array的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。