(绷不住乐， 写完看题解才知道是贪心，线段树码量是贪心正解的四五倍······)

算法

(线段树) $O(nlogn)$

一开始没有思路，也没有想到贪心正解，就试着模拟一下样例。

发现对于每一次选择(即选择出能得到最大疲劳值的那个位置S[j]):

如果前面选择过的最远的S[i]大于这一次选择的S[j]，那么本次选择的疲劳值就是上一次选择的疲劳值加上这次选择的A[j]。
如果前面选择过的最远的S[i]小于这一次选择的S[j],那么本次选择的疲劳值就是上一次选择的疲劳值加上这次选择的A[j]与 (这次选择的S[j]与之前选择过的最大S[i]的差) * 2 之和。

也就是说每一次选择的最大疲劳值都与前面的选择相关，那么就可以从第一次开始，模拟整个过程，每一步都取最大。

由于每一次选择都是区间查询最大值，自然而然想到线段树。线段树里维护的就是每次选择取到的最大疲劳值。
然而直接维护最大疲劳值并不利于线段树里信息的更新(反正我是没想到怎么更新，太拉乐)，所以想到维护每次疲劳值改变的最大增量，一次次累加最大增量得到答案。

那么怎么去解决在更新max(s[i])后，i + 1 ~ n节点的信息呢？
由于在更新max(s[i])后，i + 1 ~ n所要增加的值各不相同，最暴力的方法就是一个个全部修改掉，显然这样时间复杂度不允许。那么就掉个头，把”+”化为”-“：一开始建立线段树时就把每个节点的S * 2 + A的值塞进去, 当更新max(s[i])后，统一对i后面的节点减去2 * S[i]，即懒标记操作线段树。这样构造线段树“-”操作是与“+”操作等价的。

然后对于第一种情况，同样是不能暴力地把i之前的线段树节点修改成A的，那么就空间换时间，再造一棵保存A序列的线段树，每次查询对两棵线段树进行操作，选出来较大值加在答案里，较大值位置的节点值再清零就行了。

在这里将处理第二种情况的线段树称作0树，处理第一种情况的线段树称作1树
注意在对0树进行清零操作时，还要对1树进行清零操作，不然会对后面的模拟产生影响。
还有一些细节看代码⑧，有什么需要改进的地方还请指出。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int s[N], a[N];

struct node
{
    int l, r;
    int maxn, x, sub; //存下的X是下标，便于清零操作
}tr[2][N * 4];

void pushup(int u, int t)
{
    if (tr[t][u << 1].maxn <= tr[t][u << 1 | 1].maxn)
    {
        tr[t][u].maxn = tr[t][u << 1 | 1].maxn;
        tr[t][u].x = tr[t][u << 1 | 1].x;
    }
    else
    {
        tr[t][u].maxn = tr[t][u << 1].maxn;
        tr[t][u].x = tr[t][u << 1].x;
    }
}

void build(int u, int l, int r, int t)
{
    if (l == r)
    {
        if (!t) tr[t][u] = { l, r, a[l] + s[l] * 2, l };
        else tr[t][u] = { l, r, a[l], l };
    }
    else
    {
        tr[t][u] = { l, r };
        int mid = l + r >> 1;

        build(u << 1, l, mid, t), build(u << 1 | 1, mid + 1, r, t);
        pushup(u, t);
    }
}

void pushdown(int u, int t)
{
    if (tr[t][u].sub)
    {
        tr[t][u << 1].sub += tr[t][u].sub, tr[t][u << 1 | 1].sub += tr[t][u].sub;
        tr[t][u << 1].maxn += tr[t][u].sub, tr[t][u << 1 | 1].maxn += tr[t][u].sub;
        tr[t][u].sub = 0;
    }
}

void setzero(int u, int x, int t)
{
    if (tr[t][u].r == tr[t][u].l)
    {
        tr[t][u].maxn = 0;
    }
    else
    {
        pushdown(u, t);

        int mid = tr[t][u].l + tr[t][u].r >> 1;

        if (x <= mid) setzero(u << 1, x, t);
        else setzero(u << 1 | 1, x, t);

        pushup(u, t);
    }
}

void change(int u, int l, int r, int k, int t)
{
    if (tr[t][u].l >= l && tr[t][u].r <= r)
    {
        tr[t][u].sub += k;
        tr[t][u].maxn += k;
    }
    else
    {
        pushdown(u, t);

        int mid = tr[t][u].l + tr[t][u].r >> 1;

        if (l <= mid) change(u << 1, l, r, k, t);
        if (r > mid) change(u << 1 | 1, l, r, k, t);

        pushup(u, t);
    }
}

node ask(int u, int l, int r, int t) //返回整个节点，便于清零操作
{
    if (tr[t][u].l >= l && tr[t][u].r <= r)
    {
        return tr[t][u];
    }
    else
    {
        pushdown(u, t);

        int mid = tr[t][u].l + tr[t][u].r >> 1;
        int maxn = 0;

        if (r <= mid) return ask(u << 1, l, r, t);
        else if (l > mid) return ask(u << 1 | 1, l, r, t);
        else
        {
            node lnode, rnode ,ans;
            lnode = ask(u << 1, l, r, t);
            rnode = ask(u << 1 | 1, l, r, t);

            if (lnode.maxn >= rnode.maxn)
            {
                ans.maxn = lnode.maxn;
                ans.x = lnode.x;
            }
            else
            {
                ans.maxn = rnode.maxn;
                ans.x = rnode.x;
            }
            return ans;
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }

    for (int j = 1; j <= n; j++)
    {
        cin >> a[j];
    }

    build(1, 1, n, 0);
    build(1, 1, n, 1);

    int pos = 0;
    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        int lmaxn = 0, rmaxn = 0;
        node ll, rr;
        if (pos)
        {
            ll = ask(1, 1, max(pos - 1, 1), 1);
            lmaxn = ll.maxn;
        }

        rr = ask(1, min(pos + 1, n), n, 0);
        rmaxn = rr.maxn;

        if (lmaxn >= rmaxn)
        {
            ans += lmaxn;
            setzero(1, ll.x, 1);
        }
        else
        {
            ans += rmaxn;
            setzero(1, rr.x, 1), setzero(1, rr.x, 0);
            change(1, min(pos + 1, n), n, -(rr.x - pos) * 2, 0);
            pos = rr.x;

        }
        cout << ans << endl;
    }
}
//可能有人觉得拿数据结构一大串写贪心题本末倒置，但菜就是菜，贪心就是不会贪······