BZOJ 3938 Robot

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

Sample Output

180
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));

     }

 }

巴特西