首页 技术 正文
技术 2022年11月23日
0 收藏 881 点赞 2,126 浏览 2583 个字

题目链接:https://ac.nowcoder.com/acm/contest/992/K

题意:给一个大小为1e5的数组,由0 1组成,有两种操作,包括区间修改,将一段区间内的0换成1,1换成0; 区间查询,查询区间内连续1的数量。

思路:区间查询和区间修改,明显可以用线段树来做,我们先分析下复杂度,每次操作复杂度为logn,有m次操作(m<=1e5+1),那么总复杂度为mlogn,是可行的。

   我们用线段树维护什么呢,因为要求区间最多连续1的个数。那么需要维护区间前缀连续0/1的个数fr[0]/fr[1],区间后缀0/1的个数ba[0]/ba[1],区间连续0/1个数最大值mx[0]/mx[1]。维护连续0的个数是因为0和1可以相互转换,这样进行更新时就方便不少。懒惰标记lazy可以用异或1来更新,因为更新两次就相当与不更新。

   因为维护的元素较多,pushup和pushdown操作就稍微复杂。这题查询的方式是需要学习的,返回区间最大连续1的个数,注意考虑由左区间后缀1和右区间前缀1组合的情况。

详见代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int maxn=;struct node{
int l,r,len,fr[],ba[],mx[];
int lazy;
}tr[maxn<<];int n,m,ans,a[maxn];void pushup(int v){
if(tr[v<<].fr[]==tr[v<<].len){
tr[v].fr[]=tr[v<<].fr[]+tr[v<<|].fr[];
tr[v].fr[]=;
}
else if(tr[v<<].fr[]==tr[v<<].len){
tr[v].fr[]=tr[v<<].fr[]+tr[v<<|].fr[];
tr[v].fr[]=;
}
else{
tr[v].fr[]=tr[v<<].fr[];
tr[v].fr[]=tr[v<<].fr[];
}
if(tr[v<<|].ba[]==tr[v<<|].len){
tr[v].ba[]=tr[v<<].ba[]+tr[v<<|].ba[];
tr[v].ba[]=;
}
else if(tr[v<<|].ba[]==tr[v<<|].len){
tr[v].ba[]=tr[v<<].ba[]+tr[v<<|].ba[];
tr[v].ba[]=;
}
else{
tr[v].ba[]=tr[v<<|].ba[];
tr[v].ba[]=tr[v<<|].ba[];
}
tr[v].mx[]=max(tr[v<<].ba[]+tr[v<<|].fr[],max(tr[v<<].mx[],tr[v<<|].mx[]));
tr[v].mx[]=max(tr[v<<].ba[]+tr[v<<|].fr[],max(tr[v<<].mx[],tr[v<<|].mx[]));
}void pushdown(int v){
tr[v<<].lazy^=,tr[v<<|].lazy^=;
swap(tr[v<<].fr[],tr[v<<].fr[]);
swap(tr[v<<].ba[],tr[v<<].ba[]);
swap(tr[v<<].mx[],tr[v<<].mx[]);
swap(tr[v<<|].fr[],tr[v<<|].fr[]);
swap(tr[v<<|].ba[],tr[v<<|].ba[]);
swap(tr[v<<|].mx[],tr[v<<|].mx[]);
tr[v].lazy=;
}void build(int v,int l,int r){
tr[v].l=l,tr[v].r=r,tr[v].len=r-l+;
if(l==r){
if(a[r]){
tr[v].fr[]=,tr[v].fr[]=;
tr[v].ba[]=,tr[v].ba[]=;
tr[v].mx[]=,tr[v].mx[]=;
}
else{
tr[v].fr[]=,tr[v].fr[]=;
tr[v].ba[]=,tr[v].ba[]=;
tr[v].mx[]=,tr[v].mx[]=;
}
return;
}
int mid=(l+r)>>;
build(v<<,l,mid);
build(v<<|,mid+,r);
pushup(v);
}void update(int v,int l,int r){
if(l<=tr[v].l&&r>=tr[v].r){
swap(tr[v].fr[],tr[v].fr[]);
swap(tr[v].ba[],tr[v].ba[]);
swap(tr[v].mx[],tr[v].mx[]);
tr[v].lazy^=;
return;
}
if(tr[v].lazy) pushdown(v);
int mid=(tr[v].l+tr[v].r)>>;
if(l<=mid) update(v<<,l,r);
if(r>mid) update(v<<|,l,r);
pushup(v);
}int query(int v,int l,int r){
if(tr[v].l==l&&tr[v].r==r)
return tr[v].mx[];
if(tr[v].lazy) pushdown(v);
int mid=(tr[v].l+tr[v].r)>>;
if(r<=mid)
return query(v<<,l,r);
else if(l>mid)
return query(v<<|,l,r);
else{
int x,y,z;
x=min(tr[v<<].ba[],mid-l+)+min(tr[v<<|].fr[],r-mid);
y=query(v<<,l,mid);
z=query(v<<|,mid+,r);
return max(x,max(y,z));
}
}int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)
scanf("%d",&a[i]);
build(,,n);
scanf("%d",&m);
while(m--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==)
update(,x,y);
else
printf("%d\n",query(,x,y));
}
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141399.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,508
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,314
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站