题解 | 1or0

1or0

https://www.nowcoder.com/practice/b08001c812604203acf0bc43e54d3bdf

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N = 2e5+9;
int const inf = 1e9+7;
string s;
int n,q;
pair<int,int> block[N];
int a[N];
int cnt;


signed main()
{
	cin>>n;
	cin>>s;
	s = " " + s;
	int m = 0,last = -1,l = 1,r = 1;
	for(int i=1;i<=n;i++)
	{
		if(last == s[i] || last == -1)
		{
			last = s[i];
			r = i;
		}
		else 
		{
			if(last == '0')
			{
				block[++cnt] = make_pair(l,r);
			}
			last = s[i];
			l = i,r = i;
		}
	}
	if(last == '0') block[++cnt] = make_pair(l,r);
	for(int i=1;i<=cnt;i++)
	{
		int len = block[i].second - block[i].first + 1;
		a[i] = a[i-1] + (len + 1) * len / 2;
	}
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		if(r < block[1].first || l > block[cnt].second)
		{
			int len = r - l + 1;
			cout<<len * (len + 1) / 2<<endl;
			continue;
		}
		int pl = -1,pr = -1;
		int L = 1,R = cnt;
		while(L < R)
		{
			int m = (L + R + 1) >> 1;
			if(block[m].first > r) R = m - 1;
			else L = m;
		}
		pr = L;
		
		L = 1,R = cnt;
		while(L < R)
		{
			int m = (L + R) >> 1;
			if(block[m].second < l) L = m + 1;
			else R = m;
		}
		pl = R;
		
		int ans = 0;
		if(block[pl].first <= l && l <= block[pl].second)
		{
			int len = block[pl].second - l + 1;
			ans += len * (len + 1) / 2;
			pl++;
		}
		if(block[pr].first <= r && r <= block[pr].second)
		{
			int len = r - block[pr].first + 1;
			ans += len * (len + 1) / 2;
			pr--;
		}
		
		
		if(pl <= pr) ans += a[pr] - a[pl-1];
		int len = r - l + 1;
		cout<<max((len + 1) * len / 2 - ans,0ll)<<endl;
	}
	return 0;
}
/*
1 1
2 2 + 1
3 3 + 2 +1

*/

糖丸了,用二分求了一下左边界向右的第一个0段,右边界向左的第一个0段。

然后处理了下边界情况,即边界在一个0段中。

但是向右,向左两边遍历就可以预处理出i向左,向右的第一个0段。

全部评论

相关推荐

吴offer选手:幽默小厂
点赞 评论 收藏
分享
(黑话警告⚠️:hc=岗位数量,&nbsp;mt=导师,&nbsp;ld=直属领导,&nbsp;cr=代码审查)25年1月,我加入了字节某前端团队,并期望能在这里待到秋招并尝试转正。然而,就在上周,ld&nbsp;找我1v1,告诉我,我的能力和团队预期不太匹配,并和我劝退。晴天霹雳吗?肯定是有的。那一刻,脑子里嗡嗡作响,各种情绪翻涌。但冷静下来想想,这几个月,自己在能掌控的范围内,确实有不少地方做得不尽如人意。所以,我想把这段不算成功的经历复盘一下,希望能给同样在努力转正的你提个醒,避开我踩过的坑。一、ld&nbsp;的要求要注意刚进组时,ld就和我聊过转正的事。我当时发问:“咱们这儿有hc&nbsp;吗?”&nbsp;ld没直接回答,只是说:“看能力,能力到了...
牛客上的彭于晏:过来人告诉你,入职后要做的第一件事儿不是说主动找活儿做,你要先学会融入团队,摸清ld的性格,投其所好。然后才是展示你的能力,能力上可以说技术或者业务,以业务能力为主,技术能力为辅。优先保证自己对业务需求的开发保证质量效率,然后再谈技术的问题,不要你觉得啥啥啥不行就想着整体优化了(发现校招生最喜欢干这事儿),我工作快5年了发现搞这种的最后都没啥好的结果,产出没有还引入新的bug,校招或者实习的水平看到的问题别人看不到嘛?为什么别人不去搞?浪费时间还没收益的事儿不要去做,技术上的能力体现在对于一个新需求,在不符合现在业务发展的架构设计上,你能拿出好的技术方案同时能考虑到后续业务发展逐渐将技术架构引入合理的架构,这是一个漫长的过程而不是一次性的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务