……普及组的题目都做不出来……（；´д｀）ゞ……再这样下去要退役了啊……
不过不管怎样感觉这题还是蛮好的，也要记录一下下~
我们注意到数据的范围，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 = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k; } struct node { int id, sum; node(int x = 0, int y = 0) { 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 * 3]; void build(int u, int l, int r, int opt) { if(l == r) { T[u].id = l, T[u].sum = opt ? a[l] : 2 * S[l] + a[l]; return; } int mid = (l + r) >> 1; build(u << 1, l, mid, opt); build(u << 1 | 1, mid + 1, r, opt); T[u] = max(T[u << 1], T[u << 1 | 1]); } void clear(int u, int l, int r, int x) { int mid = (l + r) >> 1; if(l == r) { T[u] = node(0, 0); return; } if(x <= mid) clear(u << 1, l, mid, x); else clear(u << 1 | 1, mid + 1, r, x); T[u] = max(T[u << 1], T[u << 1 | 1]); } node Query(int u, int l, int r, int L, int R) { if(L > R) return node(0, 0); int mid = (l + r) >> 1; if(L > r || R < l) return node(0, 0); if(L <= l && R >= r) return T[u]; return max(Query(u << 1, l, mid, L, R), Query(u << 1 | 1, mid + 1, r, L, R)); } }T1, T2; int main() { n = read(); for(int i = 1; i <= n; i ++) S[i] = read(); for(int i = 1; i <= n; i ++) a[i] = read(); T1.build(1, 1, n, 1), T2.build(1, 1, n, 0); node P = T2.Query(1, 1, n, 1, n); last = P.id; T1.clear(1, 1, n, last), T2.clear(1, 1, n, last); printf("%d ", ans = P.sum); for(int i = 2; i <= n; i ++) { node t1 = T1.Query(1, 1, n, 1, last - 1); node t2 = T2.Query(1, 1, n, last + 1, n); t2.sum -= 2 * S[last]; node t3 = max(t1, t2); if(t1 < t2) last = t3.id, T1.clear(1, 1, n, last), T2.clear(1, 1, n, last); else T1.clear(1, 1, n, t3.id), T2.clear(1, 1, n, last); printf("%d ", ans += t3.sum); } return 0; }