#P11728. [集训队互测 2015] Robot

[集训队互测 2015] Robot

题目描述

小 q 有 nn 只机器人,一开始他把机器人放在了一条数轴上,第 ii 只机器人在 aia_i 的位置上静止,而自己站在原点。

在这之后小 q 会执行一些操作,他想要命令一个机器人向左或者向右移动 xx 格。但是机器人似乎听不清小 q 的命令,事实上它们会以每秒 xx 格的速度匀速移动。

看着自己的机器人越走越远,小 q 很着急,他想知道当前离他(原点)最远的机器人有多远。

具体的操作以及询问见输入格式。注意,不同的机器人之间互不影响,即不用考虑两个机器人撞在了一起的情况。

输入格式

共有 mm 个事件,输入将会按事件的时间顺序给出。

第一行两个正整数 n,mn,m

接下来一行 nn 个整数,第 ii 个数是 aia_i,表示第 ii 个机器人初始的位置(初始移动速度为 00)。

接下来 mm 行,每行行首是一个非负整数 tit_i,表示该事件点发生的时刻(以秒为单位)。第二个是一个字符串 SS ,代表操作的种类。数字与字符串之间用一个空格隔开。接下来的输入按 SS 的种类分类。

  1. SScommand,则接下来两个整数 ki,xik_i,x_i,表示小 q 对第 kik_i 个机器人执行了操作,该机器人的速度将会被重置,变为向数轴正方向每秒移动 xix_i 格(若 xix_i 为负数就相当于向数轴负方向每秒移动 xi\lvert x_i \rvert 格)。保证 1kin1 \leq k_i \leq n
  2. SSquery,则你需要输出当前离原点最远的机器人有多远。

保证 t1t2t2tmt_1 \leq t_2 \leq t_2 \leq \dots \leq t_m

(注:若同一时间发生多次操作,则按读入顺序依次执行)

输出格式

对于每个 query 询问,输出一行,包含一个整数表示正确的答案。

由于本题数据量较大,建议使用高效的的输入输出方式。

4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
180
280

提示

样例解释

  • 第一个命令执行时,各个机器人的位置为:20,0,20,100-20, 0, 20, 100
  • 第二个命令执行时,各个机器人的位置为:80,0,20,10080, 0, 20, 100
  • 第一个询问时,各个机器人的位置为:180,0,80,100180, 0, -80, 100
  • 第三个命令执行时,各个机器人的位置为:280,0,180,100280, 0, -180, 100
  • 第二个询问时,各个机器人的位置为:20,0,280,100-20, 0, -280, 100

数据范围

command 的个数为 CCquery 的个数为 QQ。(所以 C+Q=mC + Q = m

对于所有的事件满足 0ti1090 \leq t_i \leq 10^9,对于所有的 command 满足 xi104\lvert x_i \rvert \leq 10^4

对于所有的机器人满足 ai109\lvert a_i \rvert \leq 10^9

所有测试数据的范围和特点如下表所示:

测试点编号 数据范围 特殊限制
11 n,m2000n,m\leq 2000
22
33 n,m105n,m\leq 10^5 1xi1-1 \leq x_i \leq 1
44 n,C105n,C\leq 10^5Q5×105Q\leq 5\times 10^5 两个机器人发生碰面或者超越另一个的次数 4×105\leq 4\times 10^5
55
66 n,m105n,m\leq 10^5 不会在 ti>0t_i>0 时出现 command 操作
77
88
99 n,C105n,C\leq 10^5Q5×105Q\leq 5\times 10^5
1010