or SPJ

这个题目名称好奇怪啊。

link

构造一个长度为n的非负整数序列x，满足m个条件，第i个条件为x[li]|x[li+1]|…|x[ri]=pi。

一道比较巧妙的按位线段树题目。首先可以考虑当前位运算（也就是或）的特点，发现若区间内所有数的某一位均为0，那么答案的那一位才是0，否则就是1。于是可以考虑按位开线段树，优先满足0的那些位（把区间内的数那一位全部赋值为0），然后在做完这些事之后把其它位都赋值为1，毕竟如果这样都没法保证那些“1位”的利益那么其它方法就更别提了。最后检测一下这样构造出来的序列是否符合题意即可。

线段树只是一个辅助作用。

#include
#define zczc
const int N=100010;
const int S=30;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int m,n,an[N];

#define lc (wh<<1)
#define rc (wh<<1|1)
#define mid (t[wh].l+t[wh].r>>1)
#define num (t[wh].r-t[wh].l+1)
struct tree{
	struct node{
		int l,r;
		bool all;
	}t[N<<2];
	inline void build(int wh,int l,int r){
		t[wh].l=l,t[wh].r=r;
		if(l==r)return;
		build(lc,l,mid);
		build(rc,mid+1,r);
	}
	inline void change(int wh,int wl,int wr){
		if(t[wh].all)return;
		if(wl<=t[wh].l&&t[wh].r<=wr){t[wh].all=true;return;}
		if(wl<=mid)change(lc,wl,wr);
		if(wr>mid)change(rc,wl,wr);
		t[wh].all=t[lc].all&&t[rc].all;
	}
	inline void visit(int wh,int pl){
		if(t[wh].all)return;
		if(t[wh].l==t[wh].r){
			an[t[wh].l]|=(1<mid)an|=work(rc,wl,wr);
	return an;
}
#undef lc
#undef rc
#undef mid
#undef num

struct node{
	int l,r,data;
}a[N];

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);read(n);
	for(int i=0;i