本文主要是介绍Interesting Array CodeForces - 483D(思维+线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
We’ll call an array of n non-negative integers a[1], a[2], …, a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value should be equal to qi.
Your task is to find any interesting array of n elements or state that such array doesn’t exist.
Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as “&”, in Pascal — as “and”.
Input
The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.
Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.
Output
If the interesting array exists, in the first line print “YES” (without the quotes) and in the second line print n integers a[1], a[2], …, a[n] (0 ≤ a[i] < 230) decribing the interesting array. If there are multiple answers, print any of them.
If the interesting array doesn’t exist, print “NO” (without the quotes) in the single line.
Examples
Input
3 1
1 3 3
Output
YES
3 3 3
Input
3 2
1 3 3
1 3 2
Output
NO
一个构造题。给m个操作，使得l到r的值与起来是q。要求构造出这样的一个数组。
我们要求一个区间内的数与起来都是q，那么这个区间内的数的二进制位上都得是1。那么我们|（或）起来，就相当于把所有的位上都变成1。最后再与起来。如果是0，就不用管了。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxx=1e5+100;
struct node{int l;int r;int v;int lazy;
}p[maxx<<2];
int lr[maxx],rr[maxx],vr[maxx];
int n,m;inline void pushup(int cur)
{p[cur].v=p[cur<<1].v&p[cur<<1|1].v;
}
inline void pushdown(int cur)
{if(p[cur].lazy){p[cur<<1].lazy|=p[cur].lazy;p[cur<<1|1].lazy|=p[cur].lazy;p[cur<<1].v|=p[cur].lazy;p[cur<<1|1].v|=p[cur].lazy;p[cur].lazy=0;}
}
inline void build(int l,int r,int cur)
{p[cur].l=l;p[cur].r=r;p[cur].lazy=p[cur].v=0;if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);pushup(cur);
}
inline void update(int l,int r,int x,int cur)
{int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r){p[cur].lazy|=x;p[cur].v|=x;return ;}pushdown(cur);int mid=L+R>>1;if(r<=mid) update(l,r,x,cur<<1);else if(l>mid) update(l,r,x,cur<<1|1);else {update(l,mid,x,cur<<1);update(mid+1,r,x,cur<<1|1);}pushup(cur);
}
inline int query(int l,int r,int cur)
{int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].v;pushdown(cur);int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else return query(l,mid,cur<<1)&query(mid+1,r,cur<<1|1);
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){build(1,n,1);for(int i=1;i<=m;i++){scanf("%d%d%d",&lr[i],&rr[i],&vr[i]);update(lr[i],rr[i],vr[i],1);}int flag=1;for(int i=1;i<=m;i++){if(query(lr[i],rr[i],1)!=vr[i]){flag=0;break;}}if(flag) {puts("YES");for(int i=1;i<=n;i++)printf("%d ",query(i,i,1));printf("\n");}else puts("NO");}return 0;
}
努力加油a啊，(o)/~
这篇关于Interesting Array CodeForces - 483D(思维+线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
