P3870 [TJOI2009]开关

    • 1.2K通过
    • 2.3K提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 块状链表,块状数组,分块 枚举,暴力 概率论,统计 线段树 各省省选 2009 天津 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    现有N(2 ≤ N ≤ 100000)盏灯排成一排,从左到右依次编号为:1,2,......,N。然后依次执行M(1 ≤ M ≤ 100000)项操作,操作分为两种:第一种操作指定一个区间[a, b],然后改变编号在这个区间内的灯的状态(把开着的灯关上,关着的灯打开),第二种操作是指定一个区间[a, b],要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

    输入输出格式

    输入格式:

    第一行有两个整数N和M,分别表示灯的数目和操作的数目。接下来有M行,每行有三个整数,依次为:c, a, b。其中c表示操作的种类,当c的值为0时,表示是第一种操作。当c的值为1时表示是第二种操作。a和b则分别表示了操作区间的左右边界(1 ≤ a ≤ b ≤ N)。

    输出格式:

    每当遇到第二种操作时,输出一行,包含一个整数:此时在查询的区间中打开的灯的数目。

    输入输出样例

    输入样例#1: 复制
    4 5
    0 1 2
    0 2 4
    1 2 3
    0 2 4
    1 1 4
    
    输出样例#1: 复制
    1
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。