15011418730 LV 7 @ 2025-8-24 23:04:00

自动搬运

来自洛谷，原作者为

	MornStar O Fortuna velut luna statu variabilis......

搬运于2025-08-24 23:04:00，当前版本为作者最后更新于2024-09-07 18:55:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

D.Distorted Fate 题解

出题人题解。

Subtask 0(20 pts)

直接照着题目上的式子模拟就可以了，复杂度 $O(qn^2)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,mod=(1<<30);
int n,q,a[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1,opt,l,r,x;i<=q;i++){
		cin>>opt>>l>>r;
		if(opt==1){
			cin>>x;
			for(int j=l;j<=r;j++)	a[j]^=x;
		}else{
			long long ans=0;
			for(int j=l;j<=r;j++){
				int tmp=0;
				for(int k=l;k<=j;k++)	tmp|=a[k];
				ans=(ans+tmp)%mod;
			}
			cout<<ans<<"\n";
		}
	}
}

Subtask 1(40 pts)

发现 $\sum_{i=l}^r\bigcap_{j=l}^i A_j$ 可以在求值的时候做前缀或， $O(n)$ 回答询问，时间复杂度 $O(qn)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,mod=(1<<30);
int n,q,a[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1,opt,l,r,x;i<=q;i++){
		cin>>opt>>l>>r;
		if(opt==1){
			cin>>x;
			for(int j=l;j<=r;j++)	a[j]^=x;
		}else{
			long long ans=0,tmp=0;
			for(int j=l;j<=r;j++){
				tmp|=a[j];
				ans=(ans+tmp)%mod;
			}
			cout<<ans<<"\n";
		}
	}
}

Subtask 2(60 pts)

既然我们可以使用前缀或统计答案，说明在求和的右端点 $i$ 逐渐向右移的过程中， $\bigcap_{j=l}^i A_j$ 的的值在不断变大，而这种变化最多进行 $O(\log w)$ 次，因为一个数在二进制下最多只有 $O(\log w)$ 位为 $0$ 。

所以我们可以得到一个思路，找到答案改变的位置，这个可以很容易地使用线段树上二分做到。

考虑一个好写但时空复杂度不会变的思路，将每个数按二进制位拆开，开 $30$ 颗线段树分别维护每一位，这样，问题就转换成了寻找区间 $[l,r]$ 内的第一个 $1$ 。

从第一个 $1$ 的位置开始，直到 $r$ 这一段区间的长度乘上这一位的权值就是这一位的贡献。

线段树节点记录区间内 $1$ 的个数，以及异或标记，这个问题是容易在 $O(\log n)$ 的时间复杂度下解决的。

对每一位询问一次，需要询问 $O(\log w)$ 次，所以单次询问是 $O(\log n \log w)$ 的。

同理，单次修改也要对应修改每一位，时间复杂度也是 $O(\log n\log w)$ 的。

所以总的时间复杂度就是 $O(n\log n\log w)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,C=30,mod=1<<30;
int n,q,a[N];
struct segment_tree{
	struct segment_tree_node{int num;bool tag;}t[N<<2];
	inline int ls(int x){return x<<1;}
	inline int rs(int x){return x<<1|1;}
	inline void f(int p,int l,int r){t[p].num=(r-l+1)-t[p].num,t[p].tag^=1;}
#define mid ((l+r)>>1)
	inline void push_down(int p,int l,int r){
		if(!t[p].tag)	return;
		f(ls(p),l,mid);
		f(rs(p),mid+1,r);
		t[p].tag=0;
	}
	inline void push_up(int x){t[x].num=t[ls(x)].num+t[rs(x)].num;}
	void build(int p,int l,int r){
		if(l==r)	return t[p].num=a[l]&1,void();
		else{
			build(ls(p),l,mid);
			build(rs(p),mid+1,r);
			push_up(p);
		}
	}
	void change(int p,int l,int r,int re_l,int re_r){
		if(re_l<=l&&r<=re_r)	return f(p,l,r);
		else{
			push_down(p,l,r);
			if(re_l<=mid)	change(ls(p),l,mid,re_l,re_r);
			if(mid<re_r)	change(rs(p),mid+1,r,re_l,re_r);
			push_up(p);
		}
	}
	int find(int p,int l,int r,int k){
		if(l==r)	return l;
		else{
			push_down(p,l,r);
			if(t[ls(p)].num>=k)	return find(ls(p),l,mid,k);
			else	return find(rs(p),mid+1,r,k-t[ls(p)].num);
		}
	}
	int query(int p,int l,int r,int re_l,int re_r){
		if(re_l<=l&&r<=re_r)	return t[p].num;
		else if(!(r<re_l||l>re_r))	return push_down(p,l,r),query(ls(p),l,mid,re_l,re_r)+query(rs(p),mid+1,r,re_l,re_r);
		else	return 0;
	}
}T[30];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=0;i<C;i++){
		T[i].build(1,1,n+1);
		for(int j=1;j<=n;j++)	a[j]>>=1;
	}
	for(int i=1,opt,l,r,x;i<=q;i++){
		cin>>opt>>l>>r;
		if(opt==1){
			cin>>x;
			for(int j=0;j<C;j++){
				if(x&(1<<j))	T[j].change(1,1,n+1,l,r);
			}
		}else{
			long long ans=0;
			for(int j=0;j<C;j++){
				int num=T[j].query(1,1,n+1,1,l-1),pos=T[j].find(1,1,n+1,num+1);
				ans=(ans+(1ll<<j)*(r-min(r+1,pos)+1ll))%mod;
			}
			cout<<ans<<"\n";
		}
	}
}

Subtask 3(100pts)

Subtask 2 的做法在时间上已经足够优秀了，但是在空间上却不能满足要求。

考虑如何优化。

发现对于一个区间，我们并不关心其中 $1$ 的数量，只需要知道区间里是否有 $1$ 就行了。

我们可以在线段树节点中分别记录区间中这一位或起来的值 $x$ 和与起来的值 $y$ 。

考虑异或对区间带来的影响。

当且仅当 $x=y=1$ ，区间内全是 $1$ ，这时，区间异或会使 $x$ 和 $y$ 均变为 $0$ 。
当且仅当 $x=y=0$ ，区间内全是 $0$ ，这时，区间异或会使 $x$ 和 $y$ 均变为 $1$ 。
否则，异或不会改变 $x$ 和 $y$ 的取值。

区间内有 $1$ 等价于 $x=1$ 。

这时候，我们就可以顺利进行修改和查询操作了。

这样就可以在线段树上二分了……吗？

考虑一个问题：为什么一定要在线段树中记录 $1$ 的个数呢？

因为这个条件可以具有可差分性，所以可以用线段树上二分求解。

而我们维护的这个信息很明显没有可差分性，那应该怎么办呢？

考虑修改一下线段树上二分的步骤。

在线段树上查询区间 $[l,r]$ 时，将这个区间分成 $O(\log n)$ 段（类似于区间查询）。

按从左往右的顺序遍历每个段，这个可以在线段树上先遍历左子树，后遍历右子树实现，若遍历到这个段时，若区间里没有 $1$ 就直接返回。

否则就在这个区间里线段树上二分找到答案，然后不再遍历后面的区间，因为这个区间内线段树节点维护的信息与询问区间以外的部分无关，所以这时就不需要维护的数据满足可差分性了。

考虑时间复杂度，线段树上查询将区间分为 $O(\log n)$ 段是正常线段树区间查询的 $O(\log n)$ ，线段树上二分是 $O(\log n)$ ，但由于上面所说的剪枝，线段树的上二分的步骤实际只执行了一次，所以一次这样的操作总复杂度仍然是 $O(\log n)$ 。

于是将线段树节点内存储的一个整型变量优化成了两个布尔变量，可以顺利通过 Subtask 3。

时间复杂度仍然是 $O(n\log n\log w)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,C=30,mod=1<<30;
int n,q,a[N];
struct segment_tree{
	struct segment_tree_node{bool x,y,tag;}t[N<<2];
	inline int ls(int x){return x<<1;}
	inline int rs(int x){return x<<1|1;}
	inline void f(int p){
		if(t[p].x==t[p].y)	t[p].x^=1,t[p].y^=1;
		t[p].tag^=1;
	}
#define mid ((l+r)>>1)
	inline void push_down(int p){
		if(!t[p].tag)	return;
		f(ls(p)),f(rs(p));
		t[p].tag=0;
	}
	inline void push_up(int p){
		t[p].x=t[ls(p)].x|t[rs(p)].x;
		t[p].y=t[ls(p)].y&t[rs(p)].y;
	}
	void build(int p,int l,int r){
		if(l==r)	return t[p].x=t[p].y=a[l]&1,void();
		else{
			build(ls(p),l,mid);
			build(rs(p),mid+1,r);
			push_up(p);
		}
	}
	void change(int p,int l,int r,int re_l,int re_r){
		if(re_l<=l&&r<=re_r)	return f(p);
		else{
			push_down(p);
			if(re_l<=mid)	change(ls(p),l,mid,re_l,re_r);
			if(mid<re_r)	change(rs(p),mid+1,r,re_l,re_r);
			push_up(p);
		}
	}
	int find(int p,int l,int r){
		if(l==r)	return l;
		else{
			push_down(p);
			if(t[ls(p)].x)	return find(ls(p),l,mid);
			else	return find(rs(p),mid+1,r);
		}
	}
	int query(int p,int l,int r,int re_l,int re_r){
		if(re_l<=l&&r<=re_r){
			if(t[p].x)	return find(p,l,r);
			else	return -1;
		}else if(!(r<re_l||l>re_r)){
			push_down(p);
			int ansl=query(ls(p),l,mid,re_l,re_r);
			if(ansl!=-1)	return ansl;
			else	return query(rs(p),mid+1,r,re_l,re_r);
		}else	return -1;
	}
}T[30];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=0;i<C;i++){
		T[i].build(1,1,n+1);
		for(int j=1;j<=n;j++)	a[j]>>=1;
	}
	for(int i=1,opt,l,r,x;i<=q;i++){
		cin>>opt>>l>>r;
		if(opt==1){
			cin>>x;
			for(int j=0;j<C;j++){
				if(x&(1<<j))	T[j].change(1,1,n+1,l,r);
			}
		}else{
			long long ans=0;
			for(int j=0;j<C;j++){
				int pos=T[j].query(1,1,n+1,l,r);
				if(pos!=-1)	ans=(ans+(1ll<<j)*(r-min(r+1,pos)+1ll))%mod;
			}
			cout<<ans<<"\n";
		}
	}
}

ID

8947

时间

1000~3000ms

内存

100~512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

D.Distorted Fate 题解

Subtask 0(20 pts)

Subtask 1(40 pts)

Subtask 2(60 pts)

Subtask 3(100pts)

「QMSOI R1」 Distorted Fate

信息

1 条题解

自动搬运

以下是正文

D.Distorted Fate 题解

Subtask 0(20 pts)

Subtask 1(40 pts)

Subtask 2(60 pts)

Subtask 3(100pts)

「QMSOI R1」 Distorted Fate

信息

还没有账户？

登录