BZOJ1858 [Scoi2010]序列操作-程序员宅基地

Description

lxhgww最近收到了一个01序列,序列里面包含了n个数,这些数要么是0,要么是1,现在对于这个序列有五种变换操作和询问操作: 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作,lxhgww都需要给出回答,聪明的程序员们,你们能帮助他吗?

Input

输入数据第一行包括2个数,n和m,分别表示序列的长度和操作数目 第二行包括n个数,表示序列的初始状态 接下来m行,每行3个数,op, a, b,(0 < = op < = 4,0 < = a < = b)

Output

对于每一个询问操作,输出一行,包括1个数,表示其对应的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5
 

调试了半天 变量名打错了。。。

维护区间连续的数 类似于维护最大子段和   一下需要10个名字较长的变量把我整乱了。。。

  1 #include<cstdio>
  2 #include<algorithm>
  3 using namespace std;
  4 const int N=100000+50;
  5 int n,m,a[N];
  6 struct point{
    int ls,rs,lazy,inv,cnt,sum,lsum,rsum,sum0,lsum0,rsum0;}t[4*N];
  7 inline void print(point i)
  8  {printf("  %d %d %d %d %d %d %d %d %d\n\n",i.ls,i.rs,i.cnt,i.sum,i.lsum,i.rsum,i.sum0,i.lsum0,i.rsum0);
  9   //printf("  %d %d %d %d %d %d\n\n",i.ls,i.rs,i.cnt,i.sum,i.lsum,i.rsum);
 10  }
 11 inline void pushup(int i)
 12   {t[i].cnt=t[2*i].cnt+t[2*i+1].cnt;
 13    
 14    t[i].lsum=t[2*i].lsum; 
 15    if(t[2*i].lsum==(t[2*i].rs-t[2*i].ls+1)) t[i].lsum+=t[2*i+1].lsum;
 16    t[i].rsum=t[2*i+1].rsum;               
 17    if(t[2*i+1].rsum==(t[2*i+1].rs-t[2*i+1].ls+1)) t[i].rsum+=t[2*i].rsum;
 18     
 19    t[i].sum=max(t[2*i].rsum+t[2*i+1].lsum
 20            ,max(max(t[i].lsum,t[i].rsum)
 21            ,max(t[2*i].sum,t[2*i+1].sum))); 
 22     
 23     
 24    t[i].lsum0=t[2*i].lsum0; 
 25    if(t[2*i].lsum0==t[2*i].rs-t[2*i].ls+1) t[i].lsum0+=t[2*i+1].lsum0;
 26    t[i].rsum0=t[2*i+1].rsum0; 
 27    if(t[2*i+1].rsum0==t[2*i+1].rs-t[2*i+1].ls+1) t[i].rsum0+=t[2*i].rsum0;
 28     
 29    t[i].sum0=max(t[2*i].rsum0+t[2*i+1].lsum0
 30             ,max(max(t[i].lsum0,t[i].rsum0)
 31             ,max(t[2*i].sum0,t[2*i+1].sum0)));    
 32   }
 33 inline void pass(int i,int x)
 34   {
 35     t[i].lazy=x; t[i].inv=0; 
 36     t[i].cnt=t[i].sum=x*(t[i].rs-t[i].ls+1); t[i].sum0=(1-x)*(t[i].rs-t[i].ls+1);
 37     if(x==0)      {t[i].lsum=t[i].rsum=0; 
 38                    t[i].lsum0=t[i].rsum0=t[i].rs-t[i].ls+1;
 39                   }
 40     else if(x==1) {t[i].lsum0=t[i].rsum0=0; 
 41                    t[i].lsum=t[i].rsum=t[i].rs-t[i].ls+1;
 42                   }
 43   } 
 44 inline void fan(int i)
 45   {  if(t[i].lazy!=-1) {pass(i,t[i].lazy^1); return;}
 46      t[i].inv^=1; 
 47      t[i].cnt=t[i].rs-t[i].ls+1-t[i].cnt;
 48      swap(t[i].lsum,t[i].lsum0);
 49      swap(t[i].rsum,t[i].rsum0);
 50      swap(t[i].sum,t[i].sum0);
 51   }   
 52 inline void pushdown(int i)
 53   {
    if(t[i].lazy!=-1)
 54     {pass(2*i,t[i].lazy);
 55      pass(2*i+1,t[i].lazy);     
 56      t[i].lazy=-1;  
 57     }
 58      
 59    if(t[i].inv==1)  
 60     { t[i].inv=0;
 61       fan(2*i); fan(2*i+1);
 62     }
 63   }  
 64 void build(int i,int l,int r)
 65  {t[i].ls=l; t[i].rs=r; t[i].lazy=-1; 
 66   if(l==r) {t[i].cnt=t[i].sum=t[i].lsum=t[i].rsum=a[l]; 
 67             t[i].sum0=t[i].lsum0=t[i].rsum0=1-a[l]; 
 68              return  ;
 69            }    
 70   int mid=t[i].ls+t[i].rs>>1;
 71   build(i<<1,l,mid); build(2*i+1,mid+1,r);
 72   pushup(i);
 73  }
 74 void change(int i,int l,int r,int x)
 75  {
    if(l<=t[i].ls && t[i].rs<=r) {pass(i,x); return;}
 76   
 77   pushdown(i); int mid=t[i].ls+t[i].rs>>1;
 78   if(l<=mid) change(2*i,l,r,x);
 79   if(mid<r)  change(2*i+1,l,r,x);
 80   pushup(i);    
 81  }
 82 void rev(int i,int l,int r)
 83  {
    if(l<=t[i].ls && t[i].rs<=r) {fan(i); return;}
 84   
 85   pushdown(i); int mid=t[i].ls+t[i].rs>>1;
 86   if(l<=mid) rev(2*i,l,r);
 87   if(mid<r)  rev(2*i+1,l,r);
 88   pushup(i);    
 89  } 
 90 int ask(int i,int l,int r)
 91  {
    if(l<=t[i].ls && t[i].rs<=r) {
    return t[i].cnt;}
 92    
 93   pushdown(i); int mid=t[i].ls+t[i].rs>>1; //print(i);
 94   if(r<=mid) return ask(2*i,l,r);
 95   else if(mid<l)return ask(2*i+1,l,r);
 96   else          return ask(2*i,l,r)+ask(2*i+1,l,r);
 97  }  
 98 point hehe(int i,int l,int r)
 99  {
    if(l<=t[i].ls && t[i].rs<=r) return t[i];
100   
101   pushdown(i); int mid=t[i].ls+t[i].rs>>1;
102   
103   if(r<=mid) return hehe(2*i,l,r);
104   else if(mid<l)return hehe(2*i+1,l,r);
105   else          {point r1=hehe(2*i,l,r),r2=hehe(2*i+1,l,r),re;
106                   
107                   re.cnt=r1.cnt+r2.cnt; re.ls=r1.ls; re.rs=r2.rs;
108    
109                    re.lsum=r1.lsum; 
110                    if(r1.lsum==r1.rs-r1.ls+1) re.lsum+=r2.lsum;
111                    re.rsum=r2.rsum;
112                    if(r2.rsum==r2.rs-r2.ls+1) re.rsum+=r1.rsum;
113                     
114                    re.sum=max(r1.rsum+r2.lsum,max(max(re.lsum,re.rsum),max(r1.sum,r2.sum))); 
115                   return re;
116                 }
117  }   
118 void shuchu(int i)
119  {
    if(t[i].ls==t[i].rs) {print(t[i]); return;}
120  
121   pushdown(i); print(t[i]);
122   shuchu(2*i); shuchu(2*i+1);
123  } 
124 void que(int i)
125   {
    if(t[i].ls==t[i].rs) {printf("%d ",t[i].cnt);return;}
126   pushdown(i); 
127   que(2*i); que(2*i+1);
128  } 
129 inline int read()
130 {   int k=0,f=1;char ch=getchar();
131     while(ch<'0'||ch>'9'){
    if(ch=='-') f=-1; ch=getchar();}
132     while(ch>='0'&&ch<='9')k=k*10+ch-'0',ch=getchar();
133     return k*f;
134 } 
135 int main()
136 {
137  scanf("%d%d",&n,&m);   int op,x,y;
138  
139  for(int i=1;i<=n;i++) a[i]=read();
140  build(1,1,n); // shuchu(1);
141  //print(t[1]);
142   
143  while(m--) 
144   {op=read(); x=read(); y=read(); x++,y++;
145    
146    if(op==0)
147      { change(1,x,y,0); //shuchu(1); printf("\n\n\n");
148      }
149    else if(op==1)
150      { change(1,x,y,1); //shuchu(1); printf("\n\n\n");
151      }
152    else if(op==2)
153      { rev(1,x,y);      //shuchu(1); printf("\n\n\n");
154      }
155    else if(op==3)  
156      { printf("%d\n",ask(1,x,y));// shuchu(1); printf("\n\n\n");
157      }
158    else if(op==4)
159      { //que(1); printf("\n\n\n");
160        point ans=hehe(1,x,y); 
161        printf("%d\n",ans.sum);// shuchu(1); printf("\n\n\n");
162      }  
163   }
164 return 0;
165 }

 

 

 

转载于:https://www.cnblogs.com/YuXiaoze/p/10679508.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30437847/article/details/99404189

智能推荐

后端配置(宝塔):SSH终端设置_宝塔ssh密钥登录-程序员宅基地

本文介绍了Future接口的主要作用是用于异步处理任务,并列举了其中的方法。同时展示了运行结果,说明了futureTask.get()方法需要5秒才能返回结果,导致主线程被阻塞了5秒。

计算机考试金麦圈编号教程,计算机二级:数据处理-程序员宅基地

文章浏览阅读7.6k次。《计算机二级:数据处理》由会员分享,可在线阅读,更多相关《计算机二级:数据处理(10页珍藏版)》请在人人文库网上搜索。1、精品文库打开 Excelkt 文件夹下的 Excel14A.xlsx 工作簿文件,按下列要求操作。1、基本编辑 将Exceikt文件夹下的ScoreA.docx文件中的数据复制到Sheetl工作表A2单元格开始 处。 编辑 Sheet1 工作表A. 在最左端插入 1列,列宽10..._公式填充商品编号,商品名称有金麦圈

360路由器的虚拟服务器设置,360路由器无线万能中继设置教程图解-程序员宅基地

文章浏览阅读2.1k次。如果WiFi在很久之前就出现了,皇宫也准备安装路由器该怎么办?首先需要通过两个关卡的考验。第一关:【安全】惜命的皇上夸张到每道菜都要找专人试毒,面对有着无限可能,潜藏着DNS劫持和钓鱼网站等诸多陷阱的网络世界,安全自然是最为重要的。考虑到360安全路由有9大安全防护秘籍,过关!第二关:【信号覆盖】封建社会,为了凸显皇权的至高无上,必然会要求整个皇宫只能皇上自己使用主路由,而后妃等不能僭越。这就产生..._360路由器p4g无线中续

虎牙直播网页弹幕过滤小探索_虎牙弹幕脚本js-程序员宅基地

文章浏览阅读703次。虎牙直播网页弹幕过滤小探索没过滤前,一堆 333过滤后,舒服了js代码使用方法网页看直播时候,没发现有过滤弹幕的功能,自己摸索了一下。没过滤前,一堆 333过滤后,舒服了js代码 //过滤内容 var filterKeyWord= '333'; $("#danmudiv").unbind("DOMNodeInserted"); $("#chat-room__list").unbind("DOMNodeInserted"); /** * 清理弹幕 _虎牙弹幕脚本js

Java 自定义注解及注解读取解析--模拟框架生成SQL语句_* 1.读取类中的注解信息 *2.根据注解中包含的建表结构信息创建sql语句ja* 3.使用j-程序员宅基地

文章浏览阅读247次。Java 自定义注解及注解读取解析--模拟框架生成SQL语句假设们使用一张简单的表,结构如下:定义注解:表注解:package com.xzlf.annotation;import java.lang.annotation.ElementType;import java.lang.annotation.Retention;import java.lang.annotation.RetentionPolicy;import java.la..._* 1.读取类中的注解信息 *2.根据注解中包含的建表结构信息创建sql语句ja* 3.使用j

GDKOI 2021 提高组 Day1 第三题 回文(manachar+ST表)_gdkoi2021 day1t3-程序员宅基地

文章浏览阅读175次。GDKOI 2021 提高组 Day1 第三题 回文题目大意给出长为nnn的串,和qqq组询问,每次询问区间中的最长回文串。n,q≤5∗105n,q\le5*10^5n,q≤5∗105题解可以先用manachar求出以每个位置为中心的回文串,询问时二分答案,然后在区间中判断是否存在长度为midmidmid的回文串,用ST表维护区间最值。注意二分判断时并非在整个区间[l,r][l,r][l,r]中找最大值,而需分别将左端点右移和右端点左移大约midmidmid(因奇偶而不同)的位置,以保证找_gdkoi2021 day1t3

随便推点

pythonTensor Flow预测数据_python tensorflow 预测下一组数据-程序员宅基地

文章浏览阅读789次。通过载入csv表格数据,创建数据模型,实现梯度递减,对数据进行预测#导入tensorflowimport tensorflow as tf#导入excel处理模块import pandas as pdimport numpy as nb#导入数据可视化模块 pyplot:图形绘制模块import matplotlib.pyplot as mpl数据载入data = pd.read_csv('yq.csv')x = nb.array(data.get('date'))y = nb.a_python tensorflow 预测下一组数据

使用a标签创建引入js中的方法_a标签导入外部js-程序员宅基地

文章浏览阅读704次。1. a href="javascript:js_method();" 这是平台上常用的方法,但是这种方法在传递this等参数的时候很容易出问题,而且javascript:协议作为a的href属性的时候不仅会导致不必要的触发window.onbeforeunload事件,在IE里面更会使gif动画图片停止播放。W3C标准不推荐在href里面执行javascript语句 2. a h_a标签导入外部js

小程序怎么自定义导航栏,导航栏放图片、设置高度_小程序自定义导航栏-程序员宅基地

文章浏览阅读1.1w次,点赞4次,收藏28次。这样就搞定了,希望你们的logo比我的好看。今天来说一下小程序的自定义导航栏。_小程序自定义导航栏

Introduction to Robotics 总结1~6-程序员宅基地

文章浏览阅读6.8k次,点赞4次,收藏32次。机器人学中经典教材 《Introduction to Robotics: Mechanics and Control》,也就是John Craig的中文版《机器人学导论》,刚来实验室的时候,就发现师兄们人手一本了,某些章节自己啃也是有点难度的,之前在 Youtube上看完了斯坦福 Oussama Khatib 教授的视频Introduction to Robotics,他们上课使用的教材就是这本,一共十六篇lecture,讲解也是很通俗易懂,涵盖了机器人坐标变化、D-H参数建模、动力学、运动学、PD、PI._introduction to robotics

【HDU3038】How Many Answers Are Wrong(带权并查集)_tt and ff are ... friends. uh... very very good fr-程序员宅基地

文章浏览阅读146次。题目链接 How Many Answers Are Wrong Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15260 Accepted Submission(s): 5361 Proble..._tt and ff are ... friends. uh... very very good friends -________-b ff is a

库文件整理-程序员宅基地

文章浏览阅读110次。纸上得来终觉浅,绝知此事要躬行。C系统提供了丰富的系统文件,称为库文件。C的库文件分为两类,一类是扩展名为‘.h’的文件,称为头文件。在该类文件中包含了常量的定义、类型定义、宏定义、函数原型及各种编译选择设置等信息。另一类是库函数,包含了各种函数的目标代码,供用户在程序中调用。通常在程序中调用一个库函数时,要在调用之前包含该函数原型所在的.h文件。alloc.h 内存管理..._库文件整理

推荐文章

热门文章

相关标签