TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3059
  • 题目
  • P3059【线段树】细胞分裂剂
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    实验室里有n种细胞,它们被排成了一行,从左往右编号1到n。我们可以用细胞分裂剂使一段区间的细胞分裂成两倍。
    例如,对于这一行细胞 {1 2 3 3 4 5}, 我们在区间[2,5]使用分裂剂后就变成了 {1 2 2 3 3 3 3 4 4 5}.
    在经过若干次操作后,请你找出指定区间中,哪种细胞的数量最多。

    输入格式

    第一行,两个整肃n和m分别表示细胞的种数和操作的数量。 (1 <= n,m<= 50000)
    解下来m行,每行描述一个操作。有两种操作:
    Q l r,询问区间[l,r]的,数量最多的哪种细胞的个数
    D l r, 使用分裂剂将区间[l,r]的细胞分裂成两倍


    0 <= r – l <= 10^8, 1 <= l, r <= 细胞的数量

    输出格式

    对于每个询问,输出一行,一个整数,表示结果。

    样例输入

    5 5
    D 5 5
    Q 5 6
    D 2 3
    D 1 2
    Q 1 7

    样例输出

    2
    3


    来源  2014 Multi