https://codeforces.com/problemset/problem/482/B
We'll call an array of nn non-negative integers a\[1\],a\[2\],...,a\[n\] interesting, if it meets mm constraints. The ii -th of the mm constraints consists of three integers l_{i}li , r_{i}ri , q_{i}qi ( 1<=l_{i}<=r_{i}<=n1<=li<=ri<=n ) meaning that value should be equal to q_{i}qi .
Your task is to find any interesting array of nn elements or state that such array doesn't exist.
Expression x&y means the bitwise AND of numbers xx and yy . In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".
We'll call an array of nn non-negative integers a\[1\],a\[2\],...,a\[n\] interesting, if it meets mm constraints. The ii -th of the mm constraints consists of three integers l_{i}li , r_{i}ri , q_{i}qi ( 1<=l_{i}<=r_{i}<=n1<=li<=ri<=n ) meaning that value should be equal to q_{i}qi .
Your task is to find any interesting array of nn elements or state that such array doesn't exist.
Expression x&y means the bitwise AND of numbers xx and yy . In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".
We'll call an array of nn non-negative integers a\[1\],a\[2\],...,a\[n\] interesting, if it meets mm constraints. The ii -th of the mm constraints consists of three integers l_{i}li , r_{i}ri , q_{i}qi ( 1<=l_{i}<=r_{i}<=n1<=li<=ri<=n ) meaning that value should be equal to q_{i}qi .
Your task is to find any interesting array of nn elements or state that such array doesn't exist.
Expression x&y means the bitwise AND of numbers xx and yy . In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".
构建一个序列a,满足m条限制. 限制形如<l,r,q>: a[l]&a[l+1]&...&a[r-1]&a[r]=q;(此处'&'为位运算的and操作).
由 @Styx 提供翻译
输入 #1复制
3 1 1 3 3输出 #1复制
YES 3 3 3输入 #2复制
3 2 1 3 3 1 3 2输出 #2复制
NO思路：运用线段树维护每个区间的&结果。
比如开始给一段区间a赋值p1,那么这个区间&的结果就是p1,而且区间内每个数字与p1二进制对应的1都要是1。
那现在再来一段区间b赋值p2,那么这个区间&的结果就是p2。那么a和b区间有交集的部分如何处理?有交集的部分就是p1|p2,这样分别在两个区间中的&值都能满足p1,p2.
那用线段树维护区间的|值，区间修改打lazy标记。
然后检查是否能够找到这样的序列呢？所有操作结束之后，对于每一个操作再进行一次查询，如果与操作不符，就是no，如果都是相符的就是yes，最后输出整个区间的所有元素就可以了。
不过有个奇怪的事为啥..query的res用LL就直接出问题...(雾
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; #define INF (1e18)-1 using namespace std; const int maxn=1e5+100; typedef long long LL; LL l[maxn],r[maxn],p[maxn],n,m; struct SeamentTree{ LL l,r,add,val; }tree[maxn*4]; void pushup(LL p) { tree[p].val=tree[p*2].val&tree[p*2+1].val; } void spread(LL p) { if(tree[p].add) { tree[p*2].val|=tree[p].add; tree[p*2+1].val|=tree[p].add; tree[p*2].add|=tree[p].add; tree[p*2+1].add|=tree[p].add; tree[p].add=0; } } void build(LL p,LL l,LL r) { tree[p].l=l;tree[p].r=r; if(l==r){tree[p].val=0;return;} LL mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); pushup(p); } void change(LL p,LL l,LL r,LL d) { if(l<=tree[p].l&&r>=tree[p].r) { tree[p].val|=d; tree[p].add|=d; return; } spread(p); LL mid=(tree[p].l+tree[p].r)/2; if(l<=mid) change(p*2,l,r,d); if(r>mid) change(p*2+1,l,r,d); pushup(p); } LL query(LL p,LL l,LL r) { if(l<=tree[p].l&&r>=tree[p].r) return tree[p].val; spread(p); LL mid=(tree[p].l+tree[p].r)/2; int res=INF;///为啥LL不过阿 // debug(res); // LL ans=INF; // debug(ans); if(l<=mid) res &= query(p*2,l,r); if(r>mid) res &= query(p*2+1,l,r); return res; } bool judge() { for(LL i=1;i<=m;i++) { if(query(1,l[i],r[i])!=p[i]) return true; } cout<<"YES"<<endl; for(LL i=1;i<n;i++){ cout<<query(1,i,i)<<" "; } cout<<query(1,n,n)<<endl; return false; } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); cin>>n>>m; build(1,1,n); for(LL i=1;i<=m;i++) { cin>>l[i]>>r[i]>>p[i]; change(1,l[i],r[i],p[i]); } if(judge()) cout<<"NO"<<endl; return 0; }
