[BZOJ3938]Robot 题解
![[BZOJ3938]Robot 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180225b-1.png "180225b")
题目地址：BZOJ：Problem 3938. — Robot
题目描述
小q有n只机器人，一开始他把机器人放在了一条数轴上，第i只机器人在ai的位置上静止，而自己站在原点。在这之后小q会执行一些操作，他想要命令一个机器人向左或者向右移动x格。但是机器人似乎听不清小q的命令，事实上它们会以每秒x格的速度匀速移动。看着自己的机器人越走越远，小q很着急，他想知道当前离他（原点）最远的机器人有多远。具体的操作以及询问见输入格式。注意，不同的机器人之间互不影响，即不用考虑两个机器人撞在了一起的情况。
输入输出格式
输入格式：
共有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。（注：若同一时间发生多次操作，则按读入顺序依次执行）
输出格式：
对于每个query询问，输出一行，包含一个整数表示正确的答案。C/C++输入输出long long时请用%lld。由于本题数据量较大，建议不要使用cin/cout进行输入输出。
输入输出样例
输入样例#1：
4 5 -20 0 20 100 10 command 1 10 20 command 3 -10 30 query 40 command 1 -30 50 query
输出样例#1：
180 280
说明
样例说明：
第一个命令执行时，各个机器人的位置为：−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 \leq t_i \leq 10^9，对于所有的 command 满足 |x_i| \leq 10^4。
对于所有的机器人满足|a_i| \leq 10^9。
N, C \leq 10^5
Q \leq 5 \times 10^5
题解
首先考虑机器人的位移-时间图像一定是折线图，我们把折线拆成线段，加入标记永久化线段树里。考虑离线处理需要加入的线段，并且离散化时间。
关于标记永久化线段树存入线段的用法，这个题是一个入门题：[JSOI2008]Blue Mary开公司 题解 | KSkun’s Blog，本题也需要像这个题一样画图来观察直线间的关系，只不过那个题斜率一定为正，这个题斜率可以为负。
对于每一个询问，需要找到该询问处的最大值和最小值，因为位移可为负数，取绝对值后也可以很大。正因如此，我们需要两棵线段树，一棵存最大值，一棵存最小值。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXQ = 600005, MAXN = 100005;
inline bool isop(char c) {
return c == 'c' || c == 'q';
}
inline char readop() {
char c = fgc();
while (!isop(c)) c = fgc();
return c;
}
// global variables
struct Line {
LL k, b;
Line() {}
Line(LL k, LL b): k(k), b(b) {}
inline LL cal(LL x) {
return k * x + b;
}
};
Line lstl[MAXN];
LL n, m, N, lstt[MAXN];
struct Query {
LL time, x, k;
char op;
} ques[MAXQ];
inline bool cmp(Line l1, Line l2, LL x) { // if l1 bigger than l2 on pos x
return l1.cal(x) > l2.cal(x);
}
inline double interx(Line l1, Line l2) {
return double(l2.b - l1.b) / (l1.k - l2.k);
}
std::vector<LL> tmp;
// seg tree
#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
Line tmx[MAXQ << 2], tmn[MAXQ << 2];
bool imx[MAXQ << 2], imn[MAXQ << 2];
inline void addmx(int o, int l, int r, int ll, int rr, Line line) {
if(l >= ll && r <= rr) {
if(!imx[o]) {
tmx[o] = line;
imx[o] = true;
return;
}
LL olv = tmx[o].cal(tmp[l]), orv = tmx[o].cal(tmp[r]), nlv = line.cal(tmp[l]), nrv = line.cal(tmp[r]);
if(olv >= nlv && orv >= nrv) {
return;
}
if(olv <= nlv && orv <= nrv) {
tmx[o] = line;
return;
}
double ix = interx(tmx[o], line);
if(olv >= nlv) {
if(ix <= tmp[mid]) {
addmx(lch, l, mid, ll, rr, tmx[o]);
tmx[o] = line;
} else {
addmx(rch, mid + 1, r, ll, rr, line);
}
} else {
if(ix > tmp[mid]) {
addmx(rch, mid + 1, r, ll, rr, tmx[o]);
tmx[o] = line;
} else {
addmx(lch, l, mid, ll, rr, line);
}
}
return;
}
if(ll <= mid) addmx(lch, l, mid, ll, rr, line);
if(rr > mid) addmx(rch, mid + 1, r, ll, rr, line);
}
inline void addmn(int o, int l, int r, int ll, int rr, Line line) {
if(l >= ll && r <= rr) {
if(!imn[o]) {
tmn[o] = line;
imn[o] = true;
return;
}
LL olv = tmn[o].cal(tmp[l]), orv = tmn[o].cal(tmp[r]), nlv = line.cal(tmp[l]), nrv = line.cal(tmp[r]);
if(olv <= nlv && orv <= nrv) {
return;
}
if(olv >= nlv && orv >= nrv) {
tmn[o] = line;
return;
}
double ix = interx(tmn[o], line);
if(olv < nlv) {
if(ix <= tmp[mid]) {
addmn(lch, l, mid, ll, rr, tmn[o]);
tmn[o] = line;
} else {
addmn(rch, mid + 1, r, ll, rr, line);
}
} else {
if(ix > tmp[mid]) {
addmn(rch, mid + 1, r, ll, rr, tmn[o]);
tmn[o] = line;
} else {
addmn(lch, l, mid, ll, rr, line);
}
}
return;
}
if(ll <= mid) addmn(lch, l, mid, ll, rr, line);
if(rr > mid) addmn(rch, mid + 1, r, ll, rr, line);
}
inline LL quemx(int o, int l, int r, int x) {
LL res = -1e15;
if(imx[o]) res = std::max(res, tmx[o].cal(tmp[x]));
if(l == r) return res;
if(x <= mid) res = std::max(res, quemx(lch, l, mid, x));
if(x > mid) res = std::max(res, quemx(rch, mid + 1, r, x));
return res;
}
inline LL quemn(int o, int l, int r, int x) {
LL res = 1e15;
if(imn[o]) res = std::min(res, tmn[o].cal(tmp[x]));
if(l == r) return res;
if(x <= mid) res = std::min(res, quemn(lch, l, mid, x));
if(x > mid) res = std::min(res, quemn(rch, mid + 1, r, x));
return res;
}
// main
int main() {
n = readint();
m = readint();
for(int i = 1; i <= n; i++) {
lstl[i].b = readint();
}
for(int i = 1; i <= m; i++) {
ques[i].time = readint();
ques[i].op = readop();
if(ques[i].op == 'c') {
ques[i].x = readint();
ques[i].k = readint();
}
tmp.push_back(ques[i].time);
}
tmp.push_back(-1);
tmp.push_back(0);
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
N = tmp.size() - 1;
for(int i = 1; i <= m; i++) {
if(ques[i].op == 'c') {
LL x = ques[i].x,
lst = std::lower_bound(tmp.begin(), tmp.end(), lstt[x]) - tmp.begin(),
now = std::lower_bound(tmp.begin(), tmp.end(), ques[i].time) - tmp.begin();
addmx(1, 1, N, lst, now, lstl[x]);
addmn(1, 1, N, lst, now, lstl[x]);
lstl[x] = Line(ques[i].k, lstl[x].b + ques[i].time * (lstl[x].k - ques[i].k));
lstt[x] = ques[i].time;
}
}
for(int i = 1; i <= n; i++) {
LL lst = std::lower_bound(tmp.begin(), tmp.end(), lstt[i]) - tmp.begin();
addmx(1, 1, N, lst, N, lstl[i]);
addmn(1, 1, N, lst, N, lstl[i]);
}
for(int i = 1; i <= m; i++) {
if(ques[i].op == 'q') {
LL now = std::lower_bound(tmp.begin(), tmp.end(), ques[i].time) - tmp.begin(),
ans1 = quemx(1, 1, N, now), ans2 = -quemn(1, 1, N, now);
printf("%lld\n", std::max(ans1, ans2));
}
}
return 0;
}
