TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2961
  • 题目
  • P2961【2014湖北省队互测week1】没有人的算术
    限制 : 时间限制 : 30000 MS   空间限制 : 265536 KB
    问题描述

    万物初始之前,宇宙是无边无际混沌的黑暗,只有上帝之灵穿行其间。
    上帝对这无边的黑暗十分不满,就一挥手说:“要有光”,于是世间就有了光。从此,世间就有了昼与夜的交替。这是上帝创世的第一天。
    第二天,上帝仍不满意眼前空洞的景象,就一挥手说:“要有零”。于是世间出现了第一个数:0。
    第三天,上帝对只有0很不满意,就一挥手说:“要有非零数”。于是上帝开始创造新数,每个新数用一个已经创造出来的数的有序对表示,即:x=(xL,xR)
    于是世间出现了(0,0) , (0,(0,0)) , ((0,0),0) , ((0,0),(0,0)) , ……到了晚上,各种各样千奇百怪的数在大地上奔腾。
    (注:上帝造的这个“数” 与普通的自然数、有理数之类的不同,这种数是以如上所述的方式递归定义的,总是数对里面是数对,拆分到最后会得到不可再拆的0。)
    第四天,上帝看到各个数不分彼此,就一挥手说:“要有区别”。于是为了区分每个数,上帝定义等于:
    1.0=0。
    2.对于任意xL,xR,yL,yR,若xL=yL且xR=yR,则(xL,xR)=(yL,yR)。
    3. 对于任意x,y,x=y成立当且仅当满足以上条件之一。反之记作x≠y。
    第五天,上帝看到各个数乱成一团,就一挥手说:“要有序”。于是为了比较每个数,上帝定义小于:
    1. 对于任意x,若x≠0,则0<x。
    2. 对于任意xL,xR,yL,yR,若xL<yL,则(xL,xR)<(yL,yR)。
    3. 对于任意xL,xR,yL,yR,若xL=yL且xR<yR,则(xL,xR)<(yL,yR)。
    4. 对于任意x,y,x<y成立当且仅当满足以上条件之一。反之记作x≮y。
    在此基础上定义小于等于:x≤yx<y或x=y。容易发现:
    1. x≤y,y≤xx=y。
    2. x≤y,y≤zx≤z。
    3. x≤y或y≤x。
    进而定义:
    1. x>yy<x。
    2. x≥yx≮y。
    至此万物欣欣向荣,和睦一堂。
    第六天,由于之前沉迷与算术而忘记去造核酸和蛋白质,所以上帝没办法造人。但是上帝不甘心,就一挥手说:“要有跳蚤”,于是用泥巴捏出了神奇生物跳蚤。
    上帝用五天的时间造出天地万物,又在第六天造出了唯一的生命——跳蚤。上帝看到天地万物井然有序、生生不息,自己造的跳蚤正在开心地和数学玩耍,很高兴,便决定把第七天作为休息的日子。
    跳蚤每天的生活很简单。一天开始时,他会取一个长度为n的数组a[1],a[2],..,a[n],初始时均为0。接着他会不断地做下列两件事之一:
    1. 在头脑中产生三个正整数l,r,k,然后把a[k]重新赋值为(a[l],a[r])。
    特别地,如果l=k或r=k也是合法的,这不会导致错误,因为跳蚤总是先默默算出(a[l],a[r])再给a[k]赋值。保证1≤l,r,k≤n。
    2. 在头脑中产生两个正整数l,r,然后计算a[l],a[l+1],..,a[r-1],a[r]中的最大值。保证1≤l≤r≤n。
    跳蚤当然知道怎么做啦!但是他想考考你……

    输入格式

    第一行两个正整数n,m,表示长度为n的数组,共m个操作。接下来m行每行表示一个操作:
    1. C l r k:赋值操作,执行a[k]=(a[l],a[r])。
    2. Q l r:询问操作,计算a[l],a[l+1],..,a[r-1],a[r]中的最大值。输出最大值对应的下标。
    如果有多个最大值那么取下标最小的那一个。

    输出格式

    对于每个询问操作输出一行表示相应的结果。

    样例输入

    5 10
    C 1 1 1
    C 2 1 2
    Q 1 2
    C 4 4 4
    C 5 5 5
    Q 4 5
    Q 3 3
    C 4 2 3
    C 4 4 4
    Q 3 4

    样例输出

    2
    4
    3
    3

    提示

    所有数据中赋值操作与询问操作大约各占一半。


    来源  来自添柴网,感谢VFleaKing命题,感谢nodgd放题