【题解】NOIP2015推销员

　　……普及组的题目都做不出来……（；´д｀）ゞ……再这样下去要退役了啊……

　　不过不管怎样感觉这题还是蛮好的，也要记录一下下~

　　我们注意到数据的范围，n 是 1e5, 又有 1e5组询问，暴力大概是 \(n^{2}logn\) 的吧。这个数据范围提示我们处理一组询问的复杂度应该要控制在 \(logn\) 的范围内，所以联想到前一问的答案应该会对后面的答案产生贡献。

　　于是贪心。如果在当前已经确定了 \(x\) 个推销的地方，考虑第 \(x + 1\) 个究竟应该放在哪里。如果在到达的最远的地方的右方，疲惫值增加 \(a[i] + 2 * S[i] - S[last]\) ，如果在前方，增加 \(a[i]\) 。这样就可以每次增加一个元素，求出所需答案了。可以使用线段树来维护：

　　对我知道有更简短的，可我就是喜欢线段树怎么着？

#include <bits/stdc++.h>

using namespace std;

#define maxn 100000

int n, a[maxn], S[maxn];

int ans, last;

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct node

{

    int id, sum;

    node(int x = , int y = ) { id = x, sum = y; }

    friend bool operator <(const node& a, const node& b)

    {

        if(a.sum != b.sum) return a.sum < b.sum;

        return a.id < b.id;

    }

};

struct Segament_Tree

{

    node T[maxn * ];

    void build(int u, int l, int r, int opt)

    {

        if(l == r)

        {

            T[u].id = l, T[u].sum = opt ? a[l] :  * S[l] + a[l];

            return;

        }

        int mid = (l + r) >> ;

        build(u << , l, mid, opt); build(u <<  | , mid + , r, opt);

        T[u] = max(T[u << ], T[u <<  | ]);

    }

    void clear(int u, int l, int r, int x)

    {

        int mid = (l + r) >> ;

        if(l == r)

        {

            T[u] = node(, );

            return;

        }

        if(x <= mid) clear(u << , l, mid, x);

        else clear(u <<  | , mid + , r, x);

        T[u] = max(T[u << ], T[u <<  | ]);

    }

    node Query(int u, int l, int r, int L, int R)

    {

        if(L > R) return node(, );

        int mid = (l + r) >> ;

        if(L > r || R < l) return node(, );

        if(L <= l && R >= r) return T[u];

        return max(Query(u << , l, mid, L, R), Query(u <<  | , mid + , r, L, R));

    }

}T1, T2;

int main()

{

    n = read();

    for(int i = ; i <= n; i ++) S[i] = read();

    for(int i = ; i <= n; i ++) a[i] = read();

    T1.build(, , n, ), T2.build(, , n, );

    node P = T2.Query(, , n, , n); last = P.id;

    T1.clear(, , n, last), T2.clear(, , n, last);

    printf("%d\n", ans = P.sum);

    for(int i = ; i <= n; i ++)

    {

        node t1 = T1.Query(, , n, , last - );

        node t2 = T2.Query(, , n, last + , n);

        t2.sum -=  * S[last];

        node t3 = max(t1, t2);

        if(t1 < t2) last = t3.id, T1.clear(, , n, last), T2.clear(, , n, last);

        else T1.clear(, , n, t3.id), T2.clear(, , n, last);

        printf("%d\n", ans += t3.sum);

    }

    return ;

}