题目地址：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;
}