「雅礼集训 2018 Day7」A 题解

卡常卡了1.5h

思路

先考虑拆位，则修改相当于区间赋值0/1。

考虑线段树，一次区间赋值，修改的相当于区间内所有当前位不等于修改的位的数。

由于每次都会将区间的值赋值为一个数，所以修改时可以直接暴力修改，直到当前结点的区间内当前的位的数相等。

由于每次修改每多往下递归一次，总种类数都会减少，总共往下递归不超过 $O(n \log^2 n)$ 次。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,a[500010];
struct N{
	int mn,mx,la0,la1,c;
}tr[2000010];
void pushup(int p){
	tr[p].mn=tr[p<<1].mn&tr[p<<1|1].mn;
	tr[p].mx=tr[p<<1].mx|tr[p<<1|1].mx;
	tr[p].c=min(tr[p<<1].c,tr[p<<1|1].c);
} 
void pushdown(int p){
	int l0=tr[p].la0,l1=tr[p].la1;
	tr[p<<1].c=(tr[p<<1].c&l0)|l1;
	tr[p<<1].mn=(tr[p<<1].mn&l0)|l1;
	tr[p<<1].mx=(tr[p<<1].mx&l0)|l1;
	tr[p<<1].la0=(tr[p<<1].la0&l0)|l1;
	tr[p<<1].la1=(tr[p<<1].la1&l0)|l1;
	tr[p<<1|1].c=(tr[p<<1|1].c&l0)|l1;
	tr[p<<1|1].mn=(tr[p<<1|1].mn&l0)|l1;
	tr[p<<1|1].mx=(tr[p<<1|1].mx&l0)|l1;
	tr[p<<1|1].la0=(tr[p<<1|1].la0&l0)|l1;
	tr[p<<1|1].la1=(tr[p<<1|1].la1&l0)|l1;
	tr[p].la0=(1ll<<31)-1;tr[p].la1=0;
}
void bt(int p,int l,int r){
	tr[p].la0=(1ll<<31)-1;tr[p].la1=0;
	if(l==r){
		tr[p].mn=tr[p].mx=tr[p].c=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	bt(p<<1,l,mid);
	bt(p<<1|1,mid+1,r);
	pushup(p);
}
void change(int p,int l,int r,int x,int y,int h,int v){
	if(((tr[p].mn>>h)&1)==((tr[p].mx>>h)&1)&&((tr[p].mn>>h)&1)==v)return ;
	if(l>=x&&r<=y&&((tr[p].mn>>h)&1)==((tr[p].mx>>h)&1)){
		if((v^((tr[p].mn>>h)&1))){
			tr[p].c^=1<<h;
			tr[p].mn^=1<<h;
			tr[p].mx^=1<<h;
		}
		tr[p].la0^=(v<<h)^(tr[p].la0&(1<<h));
		tr[p].la1^=(v<<h)^(tr[p].la1&(1<<h));
		return ;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid)change(p<<1,l,mid,x,y,h,v);
	if(y>mid)change(p<<1|1,mid+1,r,x,y,h,v);
	pushup(p);
}
int find(int p,int l,int r,int x,int y){
	if(l>=x&&r<=y)return tr[p].c;
	pushdown(p);
	int mid=(l+r)>>1;
	if(y<=mid)return find(p<<1,l,mid,x,y);
	if(x>mid)return find(p<<1|1,mid+1,r,x,y);
	return min(find(p<<1,l,mid,x,y),find(p<<1|1,mid+1,r,x,y));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	bt(1,1,n);
	int op,l,r,v;
	for(int _=1;_<=q;_++){
		cin>>op;
		if(op==1){
			cin>>l>>r>>v;
			for(int i=0;i<=30;i++)if(!((v>>i)&1))change(1,1,n,l,r,i,0);
		}
		else if(op==2){
			cin>>l>>r>>v;
			for(int i=0;i<=30;i++)if((v>>i)&1)change(1,1,n,l,r,i,1);
			
		}
		else{
			cin>>l>>r;
			cout<<find(1,1,n,l,r)<<'\n'; 
		}
	}
	return 0;
}