正文开始：

阅读理解：

有一个长度为

n

序列，每个格子为

0

，现给出

Q

个次更改，将第

x

个数与

1

进行异或，求每次更改后，有多少组

(l,r)

满足：

$a_l=a_{l+1}=a_{l+2}=…=a_{r}$
$a_{l-1}=a_{r+1}=0$

思路：

这道题

2\times10^5

，查询时直接枚举是不行的，有什么办法简化呢？

其实，只需要看这个数两边的数即可。

当这个数由

1

变

0

时：

如果这个数左右两边都为 $1$ ，那就相当于把一个完整的子序列分成了两个，所以答案加一。
如果两边都为 $0$ ，说明这个子序列长度为 $1$ ，那么减去 $1$ 就没有了，所以答案减一。
如果只有一个为 $0$ ，那么这个操作只是减少了序列长度，对答案并无影响。

当这个数由

0

变成

1

时：

如果这个数左右两边都为 $1$ ，那就相当于把两个合法的的子序列合并成了一个，所以答案减一。
如果两边都为 $0$ ，说明这里原本没有一个合法序列，那么就增加了一个长度为 $1$ 的合法序列，所以答案加一。
如果只有一个为 $0$ ，那么这个操作只是增加了序列长度，对答案并无影响。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,Q;
int a[500005],ans=0;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>Q;
	while(Q--){
		int x;cin>>x;
		if(a[x-1]==a[x]&&a[x+1]==a[x])ans++;//将两个进行整合得到的结果 
		if(a[x]!=a[x-1]&&a[x]!=a[x+1])ans--;//将两个进行整合得到的结果
		a[x]^=1;
		cout<<ans<<'\n';
	}
	return 0;
}

题解：AT_abc411_c [ABC411C] Black Intervals

文章操作

正文开始：

阅读理解：

思路：

代码：

相关推荐

评论

题解：AT_abc411_c [ABC411C] Black Intervals