P3285 [SCOI2014]方伯伯的OJ

    • 262通过
    • 887提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 Treap 平衡树 线段树 2014 四川 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 256MB

题解

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

    推荐的相关题目 显示

    题目描述

    方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~n“,一开始他们按照编号排名。

    方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:

    1.操作格式为1 x y,意味着将编号为x的用户编号改为y,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证x必然出现在队列中,同时,1是一个当前不在排名中的编号。

    2.操作格式为2 x,意味着将编号为x的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为x用户的排名。

    3.操作格式为3 x,意味着将编号为x的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为x用户的排名。

    4.操作格式为4 k,意味着查询当前排名为k的用户编号,执行完该操作后需要输出当前操作用户的编号。

    但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:

    • 1 x+a y+a
    • 2 x+a
    • 3 x+a
    • 4 k+a
    • 其中a为上一次操作得到的输出,一开始a=0。

    例如:上一次操作得到的输出是5这一次操作的输入为:1 13 15因为这个输入是经过加密后的,所以你应该处理的操作是1 8 10现在你截获了方伯伯的所有操作,希望你能给出结果。

    输入输出格式

    输入格式:

    输入的第1行包含2个用空格分隔的整数n和m,表示初始用户数和操作数。此后有m行,每行是一个询问,询问格式如上所示。

    输出格式:

    输出包含m行。每行包含一个整数,其中第i行的整数表示第i个操作的输出。

    输入输出样例

    输入样例#1: 复制
    10 10
    1 2 11
    3 13
    2 5
    3 7
    2 8
    2 10
    2 11
    3 14
    2 18
    4 9
    输出样例#1: 复制
    2
    2
    2
    4
    3
    5
    5
    7
    8
    11

    说明

    对于 100% 的数据,1 <= n <= 10^8,1 <= m <= 10^5

    输入保证对于所有的操作 1,2,3,x 必然已经出现在队列中,同时对于所有操作 1,1 <= y <= 2 * 10^8,并且

    y 没有出现在队列中。

    对于所有操作 4,保证 1 <= k <= n。

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