A22698.CPU 监控

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Bob 家的机子很烂……真的很烂……

以至于看视频或者跑邪恶的暴力程序的时候,由于 CPU 使用率持续过高而宕机。Bob 需要一个程序来监视 CPU 使用率。这是一个很繁琐的过程,为了让问题更加简单,Bob 会慢慢列出今天会在用计算机时做什么事。

Bob 会干很多事,除了跑暴力程序看视频之外,还会做出去玩玩和用鼠标乱点之类的事,甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内 CPU 使用率增加或减少一个值;有的事还会直接让 CPU 使用率变为一个值。

当然 Bob 会询问:在之前给出的事件影响下,CPU 在某段时间内,使用率最高是多少。有时候 Bob 还会好奇地询问,在某段时间内 CPU 曾经的最高使用率是多少。

为了使计算精确,使用率不用百分比而用一个整数表示。

不保证 Bob 的事件列表没有出莫名的问题,使得使用率为负………………

输入格式

第一行一个正整数 TT,表示 Bob 需要监视 CPU 的总时间。

然后第二行给出 TT 个数表示在你的监视程序执行之前,Bob 干的事让 CPU 在这段时间内每个时刻的使用率达已经达到了多少。

第三行给出一个整数 EE,表示 Bob 需要做的事和询问的总数。

接下来 EE 行每行表示给出一个询问或者列出一条事件:

  • Q X Y:询问从 XXYY 这段时间内 CPU 最高使用率。
  • A X Y:询问从 XXYY 这段时间内之前列出的事件使 CPU 达到过的最高使用率。
  • P X Y Z:列出一个事件这个事件使得从 XXYY 这段时间内 CPU 使用率增加 ZZ
  • C X Y Z:列出一个事件这个事件使得从 XXYY 这段时间内 CPU 使用率变为 ZZ

时间的单位为秒,使用率没有单位。

XXYY 均为正整数(XYX\le Y),ZZ 为一个整数。

XXYY 这段时间包含第 XX 秒和第 YY 秒。

保证必要运算在有符号 32 位整数以内。

输出格式

对于每个询问,输出一行一个整数回答。

输入输出样例

  • 输入#1

    10
    -62 -83 -9 -70 79 -78 -31 40 -18 -5 
    20
    A 2 7
    A 4 4
    Q 4 4
    P 2 2 -74
    P 7 9 -71
    P 7 10 -8
    A 10 10
    A 5 9
    C 1 8 10
    Q 6 6
    Q 8 10
    A 1 7
    P 9 9 96
    A 5 5
    P 8 10 -53
    P 6 6 5
    A 10 10
    A 4 4
    Q 1 5
    P 4 9 -69

    输出#1

    79
    -70
    -70
    -5
    79
    10
    10
    79
    79
    -5
    10
    10

说明/提示

数据分布如下:

1,21,2 个数据保证 TTEE 均小于等于 10310^3

3,43,4 个数据保证只有 Q 类询问。

5,65,6 个数据保证只有 C 类事件。

7,87,8 个数据保证只有 P 类事件。

对于 100%100\% 的数据,1T,E1051\le T,E\le 10^51XYT1\le X\le Y\le T231Z<231-2^{31}\leq Z\lt 2^{31}

首页