自动搬运

查看原文

来自洛谷，原作者为

	Noby_Glds be serious

搬运于2025-08-24 22:26:49，当前版本为作者最后更新于2022-05-09 13:15:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这是我第一个不看任何题解过的蓝题。

我想把自己曲折的思考过程分享给大家。

一起深度剖析这道题。

思路

一看标签：模拟，线段树。朴实无华。

看了一下题目，很明显是让我们先找一个通解。

它是如何消除一个反面朝上的硬币的？

凡事先从简单做起，考虑只有一个硬币反面朝上。

HHHTH

很显然，想让那个反面朝上的硬币反过来，就得存在 $4$ 个反面朝上的硬币。

所以第一步，是把前面 $3$ 个硬币一起反过来，需要 $3$ 步。

TTTTH

接下来就可以把所有反面朝上的硬币全翻回来了，共需 $4$ 步。

HHHHH 完成

如果我们令 $p$ 为这个反面朝上的硬币的位置，答案就为：

$$ans=p*2-1$$

如果有两个甚至更多的硬币反面朝上呢？

HHHHTT

在这里，$k$ 的值一开始不是 $1$，而是 $2$。

所以我们会把位置为 $2$，$3$，$4$ 的硬币翻过来，位置为 $1$ 的硬币没有动。

HTTTTT

接着，$k$ 退回 $2$，并把所经过的位置上的硬币翻面。

HHHHHT

然后就只有一个硬币反面朝上了。

我们在分析过程中可以发现，若 $k$ 为反面朝上的硬币的数量，则在翻硬币时，$k$ 会不断增加，直到位置 $k$ 上的硬币为反面，然后 $k$ 会不断减少，直到退回 $k$ 原来的值。

简的来说，就是 $k$ 不断往右移，碰到一个反面朝上的硬币则折回，向左移回到原来的位置，这个反面朝上的硬币就消除了。

这样不断地消去，直到没有反面朝上的硬币。

无解的情况怎么判断？

无解的情况只有一种，就是 $k$ 不断向右移，却一直没碰到反面朝上的硬币。

也就是说，在位置 $k$ 的左边有 $k$ 个硬币反面朝上。

可左边一共就 $k-1$ 个位置！

所以令我们惊异的是，无解的情况不存在！

坏坏的出题人。

答案公式？

我们模拟一下这个场景。

此时一共有 $m$ 个硬币反面朝上，$k$ 的值目前为 $m$。

$k$ 往右移，碰到一个反面朝上的硬币，再折回来。

若这个硬币的位置为 $w_1$，则这个操作所用步数为：$w_1*2-1-2*(m-1)=w_1*2-m*2+1$

然后 $m$ 值减 $1$，但我们不让它减，让它在接下来的操作中体现,此时 $k$ 的初始值更新为 $m-1$。

接着又碰到一个反面朝上的硬币，若这个硬币的位置为 $w_2$，则这个操作所用步数为：$w_2*2-1-2*(m-2)=w_2*2-(m-1)*2+1$

以此类推。

把所有的操作的步数推出来后，相加得：

$$2*(w_1+w_2+...+w_{m-1}+w_m)-2(m+(m-1)+...+2+1)+m*1 $$$$2*\sum\limits_{i=1}^mw_i-2(m+1)*m/2+m$$ $$2*\sum\limits_{i=1}^mw_i-(m+1)*m+m$$ $$2*\sum\limits_{i=1}^mw_i-m^2$$

所以，我们做到了……

等等，怎么维护 $2*\sum_{i=1}^mw_i$ 和 $m^2$？

看到这种区间异或的题目，我们会想到P3870 [TJOI2009] 开关这道题。

先切了这道题，拿着 AC 的线段树代码，公式一套，就完成啦！

代码

#include<bits/stdc++.h>
#define N 1000010
#define int long long//不开 long long 见祖宗
using namespace std;
struct hhh{
	int l,r,cnt,sum,lz;
}dl[N*4];
int n,m,l,r;
int a[N];
char p;
void pushup(int bh){
	dl[bh].cnt=dl[bh*2].cnt+dl[bh*2+1].cnt;
	dl[bh].sum=dl[bh*2].sum+dl[bh*2+1].sum;
}
void pushdown(int bh){
	if(!dl[bh].lz) return;
	dl[bh*2].lz^=1;
	dl[bh*2].cnt=dl[bh*2].r-dl[bh*2].l+1-dl[bh*2].cnt;
	dl[bh*2].sum=(dl[bh*2].r+dl[bh*2].l)*(dl[bh*2].r-dl[bh*2].l+1)/2-dl[bh*2].sum;
	dl[bh*2+1].lz^=1;
	dl[bh*2+1].cnt=dl[bh*2+1].r-dl[bh*2+1].l+1-dl[bh*2+1].cnt;
	dl[bh*2+1].sum=(dl[bh*2+1].r+dl[bh*2+1].l)*(dl[bh*2+1].r-dl[bh*2+1].l+1)/2-dl[bh*2+1].sum;
	dl[bh].lz=0;
}
void build(int bh,int l,int r){
	dl[bh].l=l,dl[bh].r=r;
	if(l==r){
		if(a[l]) dl[bh].cnt=1,dl[bh].sum=l;
		return;
	}
	int mid=(l+r)>>1;
	build(bh*2,l,mid),build(bh*2+1,mid+1,r);
	pushup(bh);
}
void update(int bh,int L,int R){
	int l=dl[bh].l,r=dl[bh].r;
	if(l>=L&&r<=R){
		dl[bh].lz^=1;
		dl[bh].cnt=r-l+1-dl[bh].cnt;
		dl[bh].sum=(r+l)*(r-l+1)/2-dl[bh].sum;
		return;
	}
	pushdown(bh);
	int mid=(l+r)>>1;
	if(L<=mid) update(bh*2,L,R);
	if(R>mid) update(bh*2+1,L,R);
	pushup(bh);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>p;
		if(p=='T') a[i]=1;
	}
	build(1,1,n);
	cout<<2*dl[1].sum-dl[1].cnt*dl[1].cnt<<endl;
	while(m--){
		cin>>l>>r;
		update(1,l,r);
		cout<<2*dl[1].sum-dl[1].cnt*dl[1].cnt<<endl;
	}
	return 0;
}//由于我用的是cin和cout，这道题卡常又卡得紧，所以要开O2

后记

这篇题解注重于寻找通解的过程，而不是线段树怎么打。

如果有茬，欢迎向我私信。

QAQ。