CF482B （拆位思想+实现）

难度：2

看到位运算想到拆位。因为是与所以对于 \([l,r]\) 区间内在二进制下，如果它是 1 则 \([l,r]\) 区间都是 1，如果是 0 则 \([l,r]\) 区间内至少有 1 个 0。因为是区间所以不难想到用线段树处理，而线段树维护的就是区间内1的个数。

考虑如何处理。首先对于q拆位，1就为区间赋值，操作完后就找到了满足所有1的方案。再考虑有没有满足有0。如果 \([l,r]\) 区间内至少有 1 个 0，并且 \([l,r]\) 区间内都是 1，则NO,否则可以。

考虑如何实现，容易想到的是开32颗线段树时间复杂度\(32n\log n\)，我也不知道为什么不能过

再考虑把32给干了。容易发现按位区间赋值其实就是区间或

下面看了题解

那处理后面其实就是将这个区间与求出来看看是否与原数一致。因为既然所有1都满足，那么1就不用考虑了，对于其他的一起处理即可

代码写起来不难

未过

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n,m,l[100005],r[100005],q[100005],ans[100005];
inline int read(){
    char c=getchar();
    int x=0;
    while(c<48){c=getchar();}
    while(c>47)x=(x*10)+(c^48),c=getchar();
    return x;
}
inline void print(int x){
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
struct seg{
	int d[400005],la[400005];
	inline void push_up(int p){
		d[p]=d[p<<1]+d[p<<1|1];
	}
	inline void push_down(int l,int r,int p,int mid){
		if(la[p]){
			d[p<<1]=la[p]*(mid-l+1);
			d[p<<1|1]=la[p]*(r-mid);
			la[p<<1]=la[p];
			la[p<<1|1]=la[p];
			la[p]=0;
		}
	}
	inline void update(int l,int r,int p,int s,int t){
		if(l>=s&&r<=t){
			d[p]=r-l+1;
			la[p]=1;
			return;
		}
		int mid=(l+r)>>1;
		push_down(l,r,p,mid);
		if(s<=mid) update(l,mid,p<<1,s,t);
		if(t>mid) update(mid+1,r,p<<1|1,s,t);
		push_up(p);
	}
	inline int getsum(int l,int r,int p,int s,int t){
		if(l>=s&&r<=t) return d[p]; 
		int mid=(l+r)>>1,ans=0;
		push_down(l,r,p,mid);
		if(s<=mid) ans+=getsum(l,mid,p<<1,s,t);
		if(t>mid) ans+=getsum(mid+1,r,p<<1|1,s,t);
		return ans;
	}
	inline void get(int l,int r,int p,int ad){
		if(l==r){
			ans[l]+=(d[p]<<ad);
			return;
		}
		int mid=(l+r)>>1;
		push_down(l,r,p,mid);
		get(l,mid,p<<1,ad);
		get(mid+1,r,p<<1|1,ad);
	}
}s[32];
int main(){
	n=read();
	m=read();
	for(register int i=1;i<=m;i++){
		l[i]=read();
		r[i]=read();
		q[i]=read();
		for(register int j=0;(1<<j)<=q[i];j++) if(q[i]&(1<<j)) s[j].update(1,n,1,l[i],r[i]); 
	}
	for(register int i=1;i<=m;i++){
		for(register int j=0;(1<<j)<=q[i];j++){
			if(!(q[i]&(1<<j))){
				if(s[j].getsum(1,n,1,l[i],r[i])==(r[i]-l[i]+1)){
					cout<<"NO"<<endl;
					return 0;
				}
			}
		}
	}
	cout<<"YES\n";
	for(register int i=0;i<=31;i++) s[i].get(1,n,1,i); 
	for(register int i=1;i<=n;i++){
		print(ans[i]);
		putchar(' ');
	}
	
	return 0;
}//1000 1111 111

已过

#include<bits/stdc++.h>
using namespace std;
int d[400005],la[400005];
void push_up(int p){
	d[p]=d[p<<1]&d[p<<1|1];
}
void push_down(int l,int r,int p,int mid){
	if(la[p]){
		d[p<<1]|=la[p];
		d[p<<1|1]|=la[p];
		la[p<<1]|=la[p];
		la[p<<1|1]|=la[p];
		la[p]=0;
	}
}
void update(int l,int r,int p,int ad,int s,int t){
	if(l>=s&&r<=t){
		d[p]|=ad;
		la[p]|=ad;
		return;
	}
	int mid=(l+r)>>1;
	push_down(l,r,p,mid);
	if(s<=mid) update(l,mid,p<<1,ad,s,t);
	if(t>mid) update(mid+1,r,p<<1|1,ad,s,t);
	push_up(p);
}
int getsum(int l,int r,int p,int s,int t){
	if(l>=s&&r<=t){
		return d[p];
	}
	int mid=(l+r)>>1,ans=(1<<30)-1;
	push_down(l,r,p,mid);
	if(s<=mid) ans=ans&getsum(l,mid,p<<1,s,t);
	if(t>mid) ans=ans&getsum(mid+1,r,p<<1|1,s,t);
	return ans;
}
int n,m,l[100005],r[100005],q[100005],ans[100005];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i]>>q[i];
		update(1,n,1,q[i],l[i],r[i]);
	}
	for(int i=1;i<=m;i++){
		if(getsum(1,n,1,l[i],r[i])!=q[i]){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES\n";
	for(int i=1;i<=n;i++){
		cout<<getsum(1,n,1,i,i)<<" ";
	}
	
	return 0;
}//1000 1111 111