P2572 [SCOI2010]序列操作

    • 861通过
    • 2.7K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 线段树 各省省选 2010 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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都需要给出回答,聪明的程序员们,你们能帮助他吗?

    输入输出格式

    输入格式:

    输入数据第一行包括2个数,n和m,分别表示序列的长度和操作数目

    第二行包括n个数,表示序列的初始状态

    接下来m行,每行3个数,op, a, b,(0<=op<=4,0<=a<=b<n)表示对于区间[a, b]执行标号为op的操作

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    
    输出样例#1: 复制
    5
    2
    6
    5

    说明

    对于30%的数据,1<=n, m<=1000

    对于100%的数据,1<=n, m<=100000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。