P3968 [TJOI2014]电源插排

    • 73通过
    • 175提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 平衡树 概率论,统计 线段树 各省省选 2014 天津
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小M的实验室有很多电源插排。这些插排的编号从1到N,由左向右排成一排。

    每天早晨,这些插排都是没有被使用的。每当一个学生来到实验室,他就将自己的笔记本电源插到某一个未被使用的插排上。实验室的同学们都很奇怪,他们完成这个过程是这样的:首先,他们找到还没有被使用的插排的最长区间。如果有多个区间长度相同,他们就选择最靠右的那个。然后将自己的电源插到该区间的中间。如果区间长度是偶数,他们同样选择靠右的那个。当一个同学离开实验室时,他会将自己的电源拔出来。数据保证每一个同学来到实验室时,至少有一个空的插排。

    需要计算在区间[LR]已经有多少个插排被使用了。

    输入输出格式

    输入格式:

    第一行是两个整数N和Q,表示插排数量和询问数量。接下来Q行,每一行以一个整数K开头,如果K为0,接下来就是两个整数L和R(1≤L≤R≤N),表示一个询问。否则表示编号为K的学生到来或离开(K≤10^9)。K的奇数次出现表示到来,偶数次出现表示离开。每个学生的编号都是唯一的。

    输出格式:

    对于每一个询问,输出一个整数,表示询问区间内有多少个插排已经被使用。

    输入输出样例

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

    说明

    数据范围

    对于 30% 的数据,N ≤ 10^5; Q ≤ 10^3

    对于 100% 的数据,N ≤ 10^9; Q ≤ 10^5

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