P2672 [NOIP2015 普及组] 推销员 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
时间复杂度 \(O(n\log n)\) 但是常数极大，运用线段树，这题数据过水，甚至我一个写错了的线段树都能拿满（除了#3hack）。非贪心。
首先按距离大小分类，并在每一类里进行排序，这里使用vector实现，为了方便弹出我们从小到大排，这样我们只需要统计每一类的末尾值就能统计出最大值。
对于选 i 个人，就相当于我先选 i - 1 个人，再选一个人，我们要求选 1 ~ n 个人的结果，就可以利用上一个的结果，只需要选出现在最大的这个人即可。
因为有路程的问题，这我们也算在疲劳值中，那在选完一个人 u 之后就会出现几种情况，设 r 为 u 所在的距离一类，last 为当前最大距离的类；
- 如果所剩距离疲劳值 \(last \ge r\) ，那么选了 r 将不影响任何类的路程疲劳值；
- 如果所剩距离疲劳值 \(r > last\)，那么对于已经被处理过路程疲劳的类即 1~last，不用再处理，对于 last + 1 ~ r - 1 则直接把所剩路程疲劳值清零，对于 r ~ n 我们直接减去当前 r 所剩的距离疲劳值。
每次询问句询问区间最大值，保存这个最大值的来源 r，然后让这个类 r，弹出最后一个，让新的加入区间，最大值加上之前的 sum，就是当前答案。
按上面进行，需要实现区间覆盖，区间加，求区间最值。实际上区间覆盖可以用区间加代替。
而实际上我实现思路不同，我们假设第一个选了 r，如果把所有数距离疲劳都减去 \(S_r\)，那么对于 1 ~ r - 1 还需要加上 \(S[r] - S[j]\)，因为它没有那么多距离。如果只看相对大小的话，那么就相当于 1~r - 1 加上了 \(S[r] - S[j]\)，照这个思路很快就能想出上面的分类。而有所不同：
- 如果所剩距离疲劳值 \(last \ge r\) ，那么选了 r 将不影响任何类的路程疲劳值；
- 如果所剩距离疲劳值 \(r > last\)，对于已经被处理过路程疲劳的类即 1~last，因为不需要继续减，就相当于加上 \(S[r]\)。对于 last + 1 ~ r - 1 则相当于加上 \(S[r]- S[j]\)，上面有解释。我们只看相对大小，而为了方便直接算出答案，还是把实际影响加进去即：全部减去 \(S[r]\)。
对于每一类新加入值，就相当于把线段树对应值减去当前最大maxv（即这个点的值），再加上新点值即可，别忘了 pop_back()。
按照上面进行线段树，即可。
感觉还是写麻烦了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>using namespace std;const int N = 100010, M = N * 8;int n, m, cnt;
vector<int> s[N];
int id[N];
int f[N];
int S[N];struct Nodes
{int l, r;int id, maxv;int add;
}tr[M];struct Node
{int s, a;bool operator<(const Node &W)const{return s < W.s;}
}g[N];void print(int A)
{Nodes u = tr[A];printf("%d %d %d %d %d %d %d\n", A, u.l, u.r, u.id, u.maxv, u.add);puts("");
}void pushup(Nodes &u, Nodes &l, Nodes &r)
{u.l = l.l;u.r = r.r;if (l.maxv > r.maxv) {u.maxv = l.maxv;u.id = l.id;}else{u.maxv = r.maxv;u.id = r.id;}
}void pushup(int u)
{pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void pushdown(Nodes &u, Nodes &l, Nodes &r)
{l.add += u.add;r.add += u.add;l.maxv += u.add;r.maxv += u.add;u.add = 0;
}void pushdown(int u)
{pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void build(int u, int l, int r)
{if (l == r) tr[u] = {l, r, l, s[l].back() + S[l], 0};else {tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}// print(u);
}void modify(int u, int l, int r, int add)
{if (l <= tr[u].l && tr[u].r <= r) {tr[u].add += add, tr[u].maxv += add;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u << 1, l, r, add);if (r > mid) modify(u << 1 | 1, l, r, add);pushup(u);}}Nodes query(int u, int l, int r)
{if (l <= tr[u].l && tr[u].r <= r) return tr[u];else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) return query(u << 1, l, r);else if (l > mid) return query(u << 1 | 1, l, r);else {Nodes A, B, res;A = query(u << 1, l, r);B = query(u << 1 | 1, l, r);pushup(res, A, B);return res;}}
}int main()
{cin >> n;for (int i = 1; i <= n; i ++ ) scanf("%d", &g[i].s);for (int i = 1; i <= n; i ++ ) scanf("%d", &g[i].a);int last = -1;for (int i = 1; i <= n; i ++ ) {int a = g[i].a;if (last != g[i].s) {cnt ++ ;last = g[i].s;S[cnt] = 2 * g[i].s;}s[cnt].push_back(a);}for (int j = 1; j <= cnt; j ++ ) sort(s[j].begin(), s[j].end());build(1, 1, cnt);last = 0;int sum = 0;for (int i = 1; i <= n; i ++ ){auto t = query(1, 1, cnt);int r = t.id;// cout << last << ' ' << query(1, 4, 4).maxv << endl;if (last < r){for (int j = last + 1; j < r; j ++ ){modify(1, j, j, S[r] - S[j]);}if (last) modify(1, 1, last, S[r]);modify(1, 1, cnt, -S[r]);//实际上这两句可以合并为//modify(1, last + 1, cnt, -S[r]);}last = max(last, r);modify(1, r, r, -s[r].back()); s[r].pop_back();if (s[r].size()) modify(1, r, r, s[r].back());else modify(1, r, r, -0x3f3f3f3f);sum += t.maxv;cout << sum << '\n';}return 0;}
