P8454 「SWTR-8」补题计划

· · 题解

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

数据范围

对于 100\% 的数据：

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;
}