自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:13，当前版本为作者最后更新于2022-08-04 11:01:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P8454 「SWTR-8」补题计划

题目描述

小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。

同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。

小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为

$$\begin{cases} inc & |x_i - w| \leq b_1 \\ 0 & b_1 < |x_i - w| \leq b_2 \\ dec & |x_i - w| > b_2 \\ \end{cases} $$

保证 $b_1 \leq b_2$ 且 $dec < 0 < inc$。

此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。

小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。

数据范围

• Subtask #1（7 points）：$n, q\leq 100$。
• Subtask #2（12 points）：$n, q\leq 500$。依赖 Subtask #1。
• Subtask #3（20 points）：$n, q\leq 4 \times 10 ^ 3$。依赖 Subtask #2。
• Subtask #4（25 points）：$w, x_i \leq 100$。
• Subtask #5（11 points）：$l = 1$，$h = 0$。
• Subtask #6（15 points）：$w, x_i \leq 10 ^ 5$。依赖 Subtask #4。
• Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。

对于 $100\%$ 的数据：

• $1\leq n, q \leq 10 ^ 5$。
• $0\leq w, x_i \leq 10 ^ 9$，$0\leq b_1 \leq b_2$ 且 $b_2$ 不大于 $w, x_i$ 上界的一半。
• $-10 ^ 4 \leq dec < 0 < inc \leq 10 ^ 4$。
• $1\leq l, il_i, ih_j \leq n$，$0 \leq h < n$，$l + h\leq 5$。
• 保证 $il$，$ih$ 递增，且一组询问每个下标至多出现一次。

Sol 1

考虑 $n, q \leq 500$。

容易发现，讨厌的题将序列割成若干连续段。连续段之间独立，因此单独考虑一个连续段。

对于当前区间 $[l, r]$，枚举其所有子区间，检查是否有喜欢的题落在其中并更新答案。

时间复杂度 $\mathcal{O}(n ^ 2q)$。

Sol 2

考虑 $n, q \leq 4\times 10 ^ 3$。

注意到对于每个位置，合法的右端点形成一段区间 $[l, r)$，从 $p$ 右边第一个喜欢的题 $l$ 开始，第一个讨厌的题 $r$ 结束。

将区间求和差分转化为端点最值，每次改变 $w$ 时暴力重新求前缀和，区间最值用线段树或 ST 表维护。

时间复杂度 $\mathcal{O}(nq \log n)$。

Sol 3

考虑 $x_i, w \leq 100$。

回答询问考虑直接枚举包含的喜欢的题，则对应的合法区间左右端点均为一段区间（被讨厌的题所限制）。区间查询前缀和最大最小值即可。

可能的 $w$ 仅有 $100$ 种取值。对每种 $w$ 的取值的对应序列建线段树维护之。

时间复杂度 $\mathcal{O}(nw + q\log n)$。

Sol 4

考虑正解。

当 $w$ 从 $1$ 增大到 $10 ^ 9$ 时，仅有 $\mathcal{O}(n)$ 次改变某个位置上的贡献的操作。

单点修改相当于对前缀和区间修改，将所有询问离线回答，用线段树维护区间加法区间最值。

时间复杂度 $\mathcal{O}(n(l\log n + h))$，空间复杂度线性。

参考代码

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 1e5 + 5;
int S, n, q, w, b1, b2, inc, dec;
struct event {
  int type, x, id, dt;
  bool operator < (const event &rhs) {
    if(x != rhs.x) return x < rhs.x;
    return type < rhs.type;
  }
} c[N * 5];
int cnt, ans[N];
vector<int> l[N], h[N];
int laz[N << 2], mx[N << 2], mn[N << 2];
void tag(int x, int v) {laz[x] += v, mx[x] += v, mn[x] += v;}
void down(int x) {if(laz[x]) tag(x << 1, laz[x]), tag(x << 1 | 1, laz[x]), laz[x] = 0;}
void push(int x) {
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
  mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
void build(int l, int r, int x) {
  if(l == r) return mx[x] = mn[x] = ::dec * l, void();
  int m = l + r >> 1;
  build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
  push(x);
}
void modify(int l, int r, int ql, int qr, int x, int v) {
  if(ql <= l && r <= qr) return tag(x, v);
  int m = l + r >> 1;
  down(x);
  if(ql <= m) modify(l, m, ql, qr, x << 1, v);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
  push(x);
}
int query(int l, int r, int ql, int qr, int x, int type) {
  int ans = type ? -1e9 : 1e9;
  if(ql > qr) return ans;
  if(ql <= l && r <= qr) return type ? mx[x] : mn[x];
  int m = l + r >> 1;
  down(x);
  if(ql <= m) ans = query(l, m, ql, qr, x << 1, type);
  if(m < qr) {
    int v = query(m + 1, r, ql, qr, x << 1 | 1, type);
    ans = type ? max(ans, v) : min(ans, v);
  }
  return ans;
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  cin >> S;
  cin >> n >> q >> w >> b1 >> b2 >> inc >> ::dec;
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    c[++cnt] = {1, x - b2, i, -::dec};
    c[++cnt] = {1, x - b1, i, inc};
    c[++cnt] = {1, x + b1 + 1, i, -inc};
    c[++cnt] = {1, x + b2 + 1, i, ::dec};
  }
  for(int i = 1; i <= q; i++) {
    int op, L, H, il, ih;
    cin >> op;
    if(op == 2) {cin >> w; continue;}
    cin >> L >> H;
    while(L--) cin >> il, l[i].push_back(il);
    while(H--) cin >> ih, h[i].push_back(ih);
    c[++cnt] = {2, w, i};
  }
  sort(c + 1, c + cnt + 1);
  build(0, n, 1);
  for(int i = 1; i <= cnt; i++) {
    event t = c[i];
    if(t.type == 2) {
      int id = t.id, res = -1e9, lst = 0, pt = 0;
      h[id].push_back(n + 1);
      for(int it : l[id]) {
        while(it > h[id][pt]) lst = h[id][pt++];
        res = max(res, query(0, n, it, h[id][pt] - 1, 1, 1) - query(0, n, lst, it - 1, 1, 0));
      }
      ans[id] = res;
    }
    else modify(0, n, t.id, n, 1, t.dt);
  }
  for(int i = 1; i <= q; i++) if(l[i].size()) printf("%d\n", ans[i]);
  return 0;
}