自动搬运

查看原文

来自洛谷，原作者为

	bcdmwSjy ‎

搬运于2025-08-24 23:17:42，当前版本为作者最后更新于2025-06-07 13:16:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛后 4min 过题什么水平 /fn。

首先我们发现谁获胜取决于最后一个 $1$ 是谁操作的，在遍历时记录上一个 $1$ 的位置并计算贡献，我们可以写出一份简单的暴力代码：

ll sum=0;
int lst=0;
for (int i=1;i<=n;i++){
	if (a[i]) lst=i;
	else sum+=i-lst; // 0 的连续段
	sum+=(lst+1)>>1; // 除以 2 是因为只有一半的情况会获胜
}
cout<<sum<<"\n";

这样复杂度为 $O(nq)$，我们考虑如何优化。

我们把贡献拆成两份，一个计算 $0$ 连续段的个数，一个计算 (lst+1)>>1 的贡献。

然后这里又有区间反转操作，考虑用线段树维护。

线段树每个节点维护前面/后面连续 $0/1$ 的个数、$0/1$ 连续段的个数、先手/后手 $1$ 处贡献的总和，共 $8$ 项内容。

然后基于上面的描述，我们可以写出 pushup。

void pushup(int i){
	tr[i].sum0=tr[ls].sum0+tr[rs].sum0+tr[ls].r0*tr[rs].l0;
	tr[i].sum1=tr[ls].sum1+tr[rs].sum1+tr[ls].r1*tr[rs].l1;
	// 0/1 连续段个数
	tr[i].l0=(tr[ls].l0==tr[ls].len?tr[ls].len+tr[rs].l0:tr[ls].l0);
	tr[i].l1=(tr[ls].l1==tr[ls].len?tr[ls].len+tr[rs].l1:tr[ls].l1);
	tr[i].r0=(tr[rs].r0==tr[rs].len?tr[rs].len+tr[ls].r0:tr[rs].r0);
	tr[i].r1=(tr[rs].r1==tr[rs].len?tr[rs].len+tr[ls].r1:tr[rs].r1);
	// 前后连续 0/1 数量
	tr[i].ans0=tr[ls].ans0+tr[rs].ans0;
	if (tr[ls].r0!=tr[ls].len) tr[i].ans0+=tr[rs].l0*ll((tr[ls].r-tr[ls].r0+1)>>1);
	tr[i].ans1=tr[ls].ans1+tr[rs].ans1;
	if (tr[ls].r1!=tr[ls].len) tr[i].ans1+=tr[rs].l1*ll((tr[ls].r-tr[ls].r1+1)>>1); // 注意：全是 0 时不能算入贡献
	// 先手/后手 1 处贡献
}

区间修改时只需要打上标记然后交换 $0/1$ 数据即可。

void pushdown(int i){
	if (tr[i].tag){
		swap(tr[ls].l0,tr[ls].l1);
		swap(tr[ls].r0,tr[ls].r1);
		swap(tr[ls].sum0,tr[ls].sum1);
		swap(tr[ls].ans0,tr[ls].ans1);
		tr[ls].tag^=1;

		swap(tr[rs].l0,tr[rs].l1);
		swap(tr[rs].r0,tr[rs].r1);
		swap(tr[rs].sum0,tr[rs].sum1);
		swap(tr[rs].ans0,tr[rs].ans1);
		tr[rs].tag^=1;

		tr[i].tag=0;
	}
}

void update(int i,int l,int r){
	if (tr[i].l>=l and tr[i].r<=r){
		swap(tr[i].l0,tr[i].l1);
		swap(tr[i].r0,tr[i].r1);
		swap(tr[i].sum0,tr[i].sum1);
		swap(tr[i].ans0,tr[i].ans1);
		tr[i].tag^=1;
		return;
	}
	pushdown(i);
	if (tr[ls].r>=l) update(ls,l,r);
	if (tr[rs].l<=r) update(rs,l,r);
	pushup(i);
}

建树时在对应位置上设置初始值就好了。

void build(int i,int l,int r){
	memset(&tr[i],0,sizeof(tr[i]));
	tr[i].l=l;
	tr[i].r=r;
	tr[i].len=r-l+1;
	if (l==r){
		if (a[l]==0) tr[i].l0=tr[i].r0=1,tr[i].sum0=1,tr[i].ans1=(l+1)>>1;
		else tr[i].l1=tr[i].r1=1,tr[i].sum1=1,tr[i].ans0=(l+1)>>1;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(i);
}

由于查询是全局的，所以每次可以直接输出 tr[1].sum0+tr[1].ans0。

总复杂度为线段树的 $O(q\log n)$，可以通过，完整代码就不给了。最后，别忘了建树 qwq。