专栏文章

CF2103F Maximize Nor 题解

llinjunye
CF2103F题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mincikb9
此快照首次捕获于
2025/12/02 00:10
3 个月前
此快照最后确认于
2025/12/02 00:10
3 个月前
查看原文
对我而言，Nor 是一个陌生的运算，所以很多性质需要慢慢发掘。
首先考虑如何得出答案：假如我们能得出一些优秀的区间，那么我们可以上一个线段树。假设区间的左右断点为 ll 和 rr，区间的 nor 值为 vv，我们就把 anslans_l 到 ansrans_r 和 vv 取 max。
首先我们肯定要思考的一点是：如果给定了你一个区间，你会怎么快速求它的答案？显然先要拆位。
我们很快想到了一个性质：决定这一位是 00 还是 11，我们只用关心最后一段连续 00 的奇偶性。
于是我们能这么快速算：记 prei,jpre_{i,j} 表示在 ii 前面（包含 ii），最后一个满足“这个数第 jj 位是 11”的下标，没有记为 00。
我们能发现一些性质：
如果 l>prer,jl>pre_{r,j}，那么第 jj 位的值为 11，当且仅当 ll 的奇偶性和 rr 不同。
如果 l=prer,jl=pre_{r,j}，那么第 jj 位的值为 11，当且仅当 ll 的奇偶性和 rr 相同。
如果 l<prer,jl<pre_{r,j}，那么第 jj 位的值为 11，当且仅当 prer,jpre_{r,j} 的奇偶性和 rr 不同。
这样我们就能快速算了。
你以为我们只迈出了第一步？不，我们快做完了！
我们考虑固定 rr。注意到一些事实：
如果 l>prer,jl>pre_{r,j}，那么 ll 到 rr 的第 jj 位和 l+2l+2 到 rr 的第 jj 位是相同的。
如果 l<prer,jl<pre_{r,j}，那么 ll 到 rr 的第 jj 位和 l−1l-1 到 rr 的第 jj 位是相同的。也就是说这里和 ll 没有关系了。
也就是说，如果我们固定了 rr，那么区间权值的种类数是 O(k)O(k) 个的！
这就很厉害了，我们可以直接把 O(n2)O(n^2) 个区间变成 O(nk)O(nk) 个区间。
总体时间复杂度 O(nklog⁡n)O(nk\log n)。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
const int mod=1e9+7;
int n,k;
int a[N];
int pre[N][18];
int nor(int l,int r){
	int ans=0;
	for(int i=0;i<k;i++){
		if(pre[r][i]<l&&l%2!=r%2)ans|=1<<i;
		if(pre[r][i]==l&&l%2==r%2)ans|=1<<i;
		if(pre[r][i]>l&&pre[r][i]%2!=r%2)ans|=1<<i;
	}
	return ans;
}
namespace SegmentTree{
	int t[N<<2];
	int lazy[N<<2];
	#define ls(p) p<<1
	#define rs(p) p<<1|1
	void clear(int n){
		for(int i=1;i<=4*n;i++)t[i]=lazy[i]=0;
		return;
	}
	void push_up(int p){
		t[p]=max(t[ls(p)],t[rs(p)]);
		return;
	}
	void build(int l,int r,int p){
		if(l==r){
			t[p]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,ls(p));
		build(mid+1,r,rs(p));
		push_up(p);
		return;
	}
	void addlazy(int p,int x){
		t[p]=max(t[p],x);
		lazy[p]=max(lazy[p],x);
		return;
	}
	void push_down(int p){
		if(!lazy[p])return;
		addlazy(ls(p),lazy[p]);
		addlazy(rs(p),lazy[p]);
		lazy[p]=0;
		return;
	}
	void update(int L,int R,int x,int l,int r,int p){
		if(L>R)return;
		if(L<=l&&r<=R){
			addlazy(p,x);
			return;
		}
		push_down(p);
		int mid=(l+r)>>1;
		if(L<=mid)update(L,R,x,l,mid,ls(p));
		if(R>mid)update(L,R,x,mid+1,r,rs(p));
		push_up(p);
		return;
	}
	int query(int D,int l,int r,int p){
		if(l==r)return t[p];
		push_down(p);
		int mid=(l+r)>>1;
		if(D<=mid)return query(D,l,mid,ls(p));
		return query(D,mid+1,r,rs(p));
	}
}
using namespace SegmentTree;
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	clear(n);
	build(1,n,1);
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++){
			if((a[i]>>j)&1)pre[i][j]=i;
			else pre[i][j]=pre[i-1][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++){
			for(int p=-2;p<=2;p++){
				if(pre[i][j]+p<1||pre[i][j]+p>n)continue;
				update(pre[i][j]+p,i,nor(pre[i][j]+p,i),1,n,1);
			}
		}
		update(1,i,nor(1,i),1,n,1);
	}
	for(int i=1;i<=n;i++)cout<<query(i,1,n,1)<<" ";
	cout<<"\n";
	for(int i=1;i<=n;i++)for(int j=0;j<k;j++)pre[i][j]=0;
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int Tc=1;
	cin>>Tc;
	while(Tc--)solve();
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...