「bzoj3938」「UOJ88」Robot - 线段树/李超树

题目大意

    小$q$有$n$只机器人，一开始他把机器人放在了一条数轴上，第$i$只机器人在$a_i$的位置上静止，而自己站在原点。
    在这之后小$q$会执行一些操作，他想要命令一个机器人向左或者向右移动$x$格。但是机器人似乎听不清小$q$的命令，事实上它们会以每秒$x$格的速度匀速移动。
    看着自己的机器人越走越远，小$q$很着急，他想知道当前离他（原点）最远的机器人有多远。
    具体的操作以及询问见输入格式。注意，不同的机器人之间互不影响，即不用考虑两个机器人撞在了一起的情况。

---

题目分析

把时间看做$x$轴，位置看做$y$轴，建立平面直角坐标系，每个机器人的移动均是折线段，因此我们可以使用李超树维护这样的一个折线段。

然后我求直线交点似乎被卡精度了，一怒之下直接换成判断是否将原来的线段完全替换。

关于李超树，这篇博客讲的很好啊，我就偷懒不讲了。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

LL max(LL a,LL b) {
	return a>b?a:b;
}

const int maxn=100005,maxq=600005;

struct Segment {
	LL k,b;
	Segment(LL _k=0,LL _b=0):k(_k),b(_b) {}
	LL f(LL x) {
		return k*x+b;
	}
} a[maxn],b[maxn];

LL t[maxq];
int n,m,q[maxq],last[maxn];

struct Tree {
	int left,right;
	Segment s;
	Tree(int l=0,int r=0):left(l),right(r),s(Segment()) {}
};

struct Segment_Tree {
	Tree tree[maxq*4];
#define ls index<<1
#define rs index<<1|1
	void build(int index,int Left,int Right) {
		tree[index]=Tree(Left,Right);
		if(Left==Right)return;
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
	}
	void insert(int index,Segment s) {
		Segment &now=tree[index].s;
		if(now.k==0&&now.b==0)now=s;
		if(now.f(t[tree[index].left])<s.f(t[tree[index].left]))swap(now,s); //保证左端点较大
		if(tree[index].left==tree[index].right||now.k==s.k)return;
		int mid=(tree[index].left+tree[index].right)>>1;
		double x=(double)(now.b-s.b)/(s.k-now.k);
		if(x<t[tree[index].left]||x>t[tree[index].right])return;
		if(x<=t[mid])insert(ls,now),now=s;
		else insert(rs,s);
	}
	void insert(int index,int Left,int Right,Segment s) {
		if(Right<tree[index].left||Left>tree[index].right)return;
		if(Left<=tree[index].left&&Right>=tree[index].right) {
			insert(index,s);
			return;
		}
		insert(ls,Left,Right,s);
		insert(rs,Left,Right,s);
	}
	LL query(int index,int target) {
		if(target<tree[index].left||target>tree[index].right)return -LLONG_MAX;
		if(tree[index].left==tree[index].right)return tree[index].s.f(t[target]);
		return max(max(query(ls,target),query(rs,target)),tree[index].s.f(t[target]));
	}
} st;

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++) {
		a[i]=Segment(0,Get_Int());
		b[i]=Segment(0,-a[i].b);
	}
	st.build(1,0,m);
	for(int i=1; i<=m; i++) {
		t[i]=Get_Int();
		char opt=' ';
		while(!isalpha(opt))opt=getchar();
		if(opt=='q')q[i]=1;
		else {
			LL x=Get_Int(),y=Get_Int();
			st.insert(1,last[x],i,a[x]);
			st.insert(1,last[x],i,b[x]);
			last[x]=i;
			a[x]=Segment(y,a[x].k*t[i]+a[x].b-t[i]*y);
			b[x]=Segment(-a[x].k,-a[x].b);
		}
	}
	for(int i=1; i<=n; i++) {
		st.insert(1,last[i],m,a[i]);
		st.insert(1,last[i],m,b[i]);
	}
	for(int i=1; i<=m; i++)
		if(q[i])printf("%lld\n",st.query(1,i));
	return 0;
}