Description
小q有n只机器人，一开始他把机器人放在了一条数轴上，第i只机器人在ai的位置上静止，而自己站在原点。在这
之后小q会执行一些操作，他想要命令一个机器人向左或者向右移动x格。但是机器人似乎听不清小q的命令，事实
上它们会以每秒x格的速度匀速移动。看着自己的机器人越走越远，小q很着急，他想知道当前离他（原点）最远的
机器人有多远。具体的操作以及询问见输入格式。注意，不同的机器人之间互不影响，即不用考虑两个机器人撞在
了一起的情况。
Input
共有m个事件，输入将会按事件的时间顺序给出。第一行两个正整数n,m。接下来一行n个整数，第i个数是ai，表示
第i个机器人初始的位置（初始移动速度为0）。接下来m行，每行行首是一个非负整数ti，表示该事件点发生的时
刻（以秒为单位）。第二个是一个字符串S，代表操作的种类。数字与字符串之间用一个空格隔开。接下来的输入
按S的种类分类。若S是“command”（不带引号），则接下来两个整数ki,xi，表示小q对第ki个机器人执行了操作
，该机器人的速度将会被重置，变为向数轴正方向每秒移动xi格（若xi为负数就相当于向数轴负方向每秒移动∣xi
∣格）。保证1≤ki≤n。若S是“query”（不带引号），则你需要输出当前离原点最远的机器人有多远。保证t1≤
t2≤t2≤...≤tm。（注：若同一时间发生多次操作，则按读入顺序依次执行）
Output
对于每个query询问，输出一行，包含一个整数表示正确的答案。C/C++输入输出longlong时请用%lld。由于本题数
据量较大，建议不要使用cin/cout进行输入输出。
Sample Input
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
Sample Output
180
280
280
HINT
第一个命令执行时，各个机器人的位置为：−20,0,20,100。
第二个命令执行时，各个机器人的位置为：80,0,20,100。
第一个询问时，各个机器人的位置为：180,0,−80,100。
第三个命令执行时，各个机器人的位置为：280,0,−180,100。
第二个询问时，各个机器人的位置为：−20,0,−280,100。
限制与约定
设 command 的个数为 C，query 的个数为 Q。（所以 C+Q=m）
对于所有的事件满足 0≤ti≤10^9，对于所有的 command 满足 ∣xi∣≤10^4。
对于所有的机器人满足 ∣ai∣≤10^9。
N,C<=10^5
Q<=5*10^5
把时间看做x坐标，距离看做y坐标，那么就是一个一次函数
改变速度的处理可以离线，预处理出每一个一次函数所覆盖的区间
坐标太大需要离散
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long lol;
struct ZYYS
{
lol l,r,k,id,b;
};
struct rubbish
{
lol t,k,id;
bool kind;
}q[];
struct caiji
{
int p,x;
}b[];
struct Line
{
lol k,b;
bool id;
}tree1[],tree2[];
lol h[],nowb[],nowk[],a[];
lol ansmax,ansmin,T;
int n,m,num,size;
char ch[];
lol gi()
{
lol x=,flag=;
char c=getchar();
while (c<''||c>'')
{
if (c=='-') flag=-;
c=getchar();
}
while (c>=''&&c<='')
{
x=x*+c-'';
c=getchar();
}
return x*flag;
}
bool pd(Line a,Line b,lol x)
{
return a.k*x+a.b>b.k*x+b.b;
}
double cross(Line a,Line b)
{
return (a.b-b.b)/(1.0*(b.k-a.k));
}
lol cal(Line a,lol x)
{
return a.k*x+a.b;
}
void add_max(int rt,int l,int r,Line x)
{
if (l>r) return;
if (!tree1[rt].id)
{
tree1[rt]=x;
return;
}
lol f1=cal(x,h[l]);lol f2=cal(tree1[rt],h[l]);
lol f3=cal(x,h[r]);lol f4=cal(tree1[rt],h[r]);
if (f1<=f2&&f3<=f4) return;
if (f1>=f2&&f3>=f4)
{tree1[rt]=x;return;}
int mid=(l+r)/;
double p=cross(tree1[rt],x);
if (f1>=f2)
{
if (p<=h[mid]) add_max(rt<<,l,mid,x);
else add_max(rt<<|,mid+,r,tree1[rt]),tree1[rt]=x;
}
else
{
if (p>h[mid]) add_max(rt<<|,mid+,r,x);
else add_max(rt<<,l,mid,tree1[rt]),tree1[rt]=x;
}
}
void add_min(int rt,int l,int r,Line x)
{
if (l>r) return;
if (!tree2[rt].id)
{
tree2[rt]=x;
return;
}
lol f1=cal(x,h[l]);lol f2=cal(tree2[rt],h[l]);
lol f3=cal(x,h[r]);lol f4=cal(tree2[rt],h[r]);
if (f1>=f2&&f3>=f4) return;
if (f1<=f2&&f3<=f4)
{tree2[rt]=x;return;}
int mid=(l+r)/;
double p=cross(tree2[rt],x);
if (f1<=f2)
{
if (p<=h[mid]) add_min(rt<<,l,mid,x);
else add_min(rt<<|,mid+,r,tree2[rt]),tree2[rt]=x;
}
else
{
if (p>h[mid]) add_min(rt<<|,mid+,r,x);
else add_min(rt<<,l,mid,tree2[rt]),tree2[rt]=x;
}
}
void update_max(int rt,int l,int r,int L,int R,Line x)
{
if (L>R) return;
if (l>r) return;
if (l>=L&&r<=R)
{
add_max(rt,l,r,x);
return;
}
int mid=(l+r)/;
if (L<=mid) update_max(rt<<,l,mid,L,R,x);
if (R>mid) update_max(rt<<|,mid+,r,L,R,x);
}
void update_min(int rt,int l,int r,int L,int R,Line x)
{
if (L>R) return;
if (l>r) return;
if (l>=L&&r<=R)
{
add_min(rt,l,r,x);
return;
}
int mid=(l+r)/;
if (L<=mid) update_min(rt<<,l,mid,L,R,x);
if (R>mid) update_min(rt<<|,mid+,r,L,R,x);
}
void query_max(int rt,int l,int r,int x)
{
if (l>r) return;
if (tree1[rt].id) ansmax=max(ansmax,cal(tree1[rt],h[x]));
//cout<<ansmax<<endl;
if (l==r)
{
return ;
}
int mid=(l+r)/;
if (x<=mid) query_max(rt<<,l,mid,x);
else query_max(rt<<|,mid+,r,x);
return ;
}
void query_min(int rt,int l,int r,int x)
{
if (l>r) return ;
if (tree2[rt].id)
ansmin=min(ansmin,cal(tree2[rt],h[x]));
//cout<<ansmin<<endl;
if (l==r)
{
return ;
}
int mid=(l+r)/;
if (x<=mid) query_min(rt<<,l,mid,x);
else query_min(rt<<|,mid+,r,x);
return ;
}
int main()
{lol i,x,j,p;
lol k,pos;
//freopen("robot.in","r",stdin);
//freopen("robot.out","w",stdout);
n=gi();m=gi();
for (i=;i<=n;i++)
{
nowb[i]=gi();a[i]=;nowk[i]=;
}
h[]=;
for (i=;i<=m;i++)
{
q[i].t=gi();
h[i+]=q[i].t;
scanf("%s",ch);
if (ch[]=='c')
{
q[i].id=gi();q[i].k=gi();
q[i].kind=;
}
}
size=unique(h+,h+m+)-h-;
for (i=;i<=m;i++)
if (q[i].kind)
{
int x=q[i].id;
int lst=lower_bound(h+,h+size+,a[x])-h;
int now=lower_bound(h+,h+size+,q[i].t)-h;
update_max(,,size,lst,now,(Line){nowk[x],nowb[x],});
update_min(,,size,lst,now,(Line){nowk[x],nowb[x],});
//cout<<lst<<' '<<now<<' '<<nowk[x]<<' '<<nowb[x]<<endl;
nowb[x]=nowb[x]+q[i].t*(nowk[x]-q[i].k);
nowk[x]=q[i].k;a[x]=q[i].t;
}
for (i=;i<=n;i++)
{
int lst=lower_bound(h+,h+size+,a[i])-h;
update_max(,,size,lst,size,(Line){nowk[i],nowb[i],});
update_min(,,size,lst,size,(Line){nowk[i],nowb[i],});
//cout<<lst<<' '<<size<<' '<<nowk[i]<<' '<<nowb[i]<<endl;
}
for (i=;i<=m;i++)
if (q[i].kind==)
{
ansmax=;
ansmin=;
int t=lower_bound(h+,h+size+,q[i].t)-h;
query_max(,,size,t);
query_min(,,size,t);
printf("%lld\n",max(ansmax,-ansmin));
}
}