P2574 XOR的艺术

    • 1K通过
    • 2.2K提交
  • 题目提供者 worcher
  • 评测方式 云端评测
  • 标签 线段树 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    AKN觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下

    1、 拥有一个伤害串为长度为n的01串。

    2、 给定一个范围[l,r],伤害为伤害串的这个范围内中1的个数

    3、 会被随机修改伤害串中的数值,修改的方法是把[l,r]中的所有数xor上1

    AKN想知道一些时刻的伤害,请你帮助他求出这个伤害

    输入输出格式

    输入格式:

    第一行两个数n,m,表示长度为n的01串,有m个时刻

    第二行一个长度为n的01串,为初始伤害串

    第三行开始m行,每行三个数p,l,r

    若p为0,则表示当前时刻改变[l,r]的伤害串,改变规则如上

    若p为1,则表示当前时刻AKN想知道[l,r]的伤害

    输出格式:

    对于每次询问伤害,输出一个数值伤害,每次询问输出一行

    输入输出样例

    输入样例#1: 复制
    10 6
    1011101001
    0 2 4
    1 1 5
    0 3 7
    1 1 10
    0 1 4
    1 2 6
    
    输出样例#1: 复制
    3
    6
    1
    

    说明

    样例解释:

    1011101001

    1100101001

    询问[1,5]输出3

    1111010001

    询问[1,10]输出6

    0000010001

    询问[2,6]输出1

    数据范围:

    10%数据2≤n,m≤10

    另有30%数据2≤n,m≤2000

    100%数据2≤n,m≤2*10^5

    By:worcher

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