TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3784
  • 题目
  • P3784打架新系统
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    校园暴力日见泛滥,今天突然出现一堆人找ZMY约架。ZMY虽然群架能力超强,但记性却不大好。他想请你帮他开发一套新系统,统计约架的情况,并告诉她当前哪一天打群架的人最多。

    ZMY有三种请求:

    1. 告诉你有一名同学报名参与了第x天的群架
    2. 告诉你有一名同学取消报名了第x天的群架
    3. 告诉你在已有x人报名打架的所有天中最晚的一天有一名同学取消报名了当天的群架

    询问你所有n天中人数>=x的最晚的一天

    输入格式

    第一行两个整数N,M,分别表示总天数和ZMY的请求个数。

    接下来M行,每行两个整数k,x。 k表示请求类型

    数据保证取消约架的请求一定合法

    输出格式

    对于每个4请求,输出答案。

    样例输入 1

    3 5
    1 1
    1 2
    1 3
    3 1
    4 1

    样例输出 1

    2

    样例输入 2

    2 6
    1 1
    1 1
    3 2 
    4 0
    1 2
    4 1

    样例输出 2

    2
    2

    提示

    样例1:第4个操作之前3天人数分别为1,1,1

    第4个操作取消了人数为1天中最晚的一天即第三天的一次约架,3天人数分别为1,1,0

    第5个操作询问人数>=1中的最晚的一天,即第2天

     

    30%的数据保证 N,M<=1000

    另30%的数据保证 N<=50000, M<=100000 没有3操作

    100%的数据保证 N<=300000, M<=500000 取消约架的请求一定合法


    来源  ZMY