[CSP-S 2022] 策略游戏 WA 95 求助

问题讨论区 提高段
1

https://www.luogu.com.cn/problem/P8818

代码 
#include <bits/stdc++.h>
#define int long long
using type_a4 = std::array<int, 4>;
const int N = 1e5 + 10, INF = 9e9;

int n, m, q, a[N], b[N];

struct SegmentTree {
  int w[N << 2], zmax[N << 2], zmin[N << 2], fmax[N << 2], fmin[N << 2];

  bool inRange(int l, int r, int L, int R) {
    return l >= L && r <= R;
  }

  bool outRange(int l, int r, int L, int R) {
    return l > R || r < L;
  }

  void pushup(int u) {
    zmax[u] = std::max(zmax[u << 1], zmax[u << 1 | 1]);
    zmin[u] = std::min(zmin[u << 1], zmin[u << 1 | 1]);
    fmax[u] = std::max(fmax[u << 1], fmax[u << 1 | 1]);
    fmin[u] = std::min(fmin[u << 1], fmin[u << 1 | 1]);
  }

  type_a4 pushup(type_a4 x, type_a4 y) {
    type_a4 res;
    res[0] = std::max(x[0], y[0]);
    res[1] = std::min(x[1], y[1]);
    res[2] = std::max(x[2], y[2]);
    res[3] = std::min(x[3], y[3]);
    return res;
  }

  void build(int *a, int u, int l, int r) {
    if (l == r) {
      w[u] = a[l];
      if (w[u] >= 0) {
        zmax[u] = zmin[u] = w[u];
        fmax[u] = -INF;
        fmin[u] = INF;
      } else {
        zmax[u] = -INF;
        zmin[u] = INF;
        fmax[u] = fmin[u] = w[u];
      }
      return ;
    }
    int mid = l + r >> 1;
    build(a, u << 1, l, mid);
    build(a, u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  // 返回值依次返回 zmax, zmin, fmax, fmin
  type_a4 query(int u, int l, int r, int L, int R) {
    if (outRange(l, r, L, R)) return type_a4({-INF, INF, -INF, INF});
    if (inRange(l, r, L, R)) return type_a4({zmax[u], zmin[u], fmax[u], fmin[u]});
    int mid = l + r >> 1;
    return pushup(query(u << 1, l, mid, L, R), query(u << 1 | 1, mid + 1, r, L, R));
  }
} ta, tb;

signed main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i <= m; ++i) std::cin >> b[i];
  ta.build(a, 1, 1, n), tb.build(b, 1, 1, m);
  for (int l1, r1, l2, r2; q; --q) {
    std::cin >> l1 >> r1 >> l2 >> r2;
    auto x = ta.query(1, 1, n, l1, r1);
    auto y = tb.query(1, 1, m, l2, r2);
    if (abs(y[0]) != INF && abs(y[2]) != INF) { // 后手有正有负
      std::cout << std::max(x[1] * y[3], x[2] * y[0]) << '\n';
    } else if (abs(y[0]) != INF) { // 后手只有正数
      if (abs(x[0]) != INF) { // 先手有正数
        std::cout << x[0] * y[1] << '\n';
      } else { // 先手只有负数
        std::cout << x[2] * y[0] << '\n';
      }
    } else { // 后手只有负数
      if (abs(x[2]) != INF) { // 先手有负数
        std::cout << x[3] * y[2] << '\n';
      } else { // 先手只有正数
        std::cout << x[1] * y[3] << '\n';
      }
    }
  }
  std::cout.flush();
  return 0;
}

一个神奇的事情是，分数与 INF 相关，但是当 INF 达到 9\times10^9+2\times10^8 左右的时候，会 WA 更多的点。

求调/kel

2

写个对拍看看吧，这大样例看的我头皮发麻

3

好的。

4

@陶荣杰1 题目附件的大样例都过了

5

@陶荣杰1 这道题的暴力也不好写 :smiling_face_with_tear:

6

云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

测下这个

7

主，，

8

暴力挂了 :smiling_face_with_tear:

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 10, INF = 1e18;

int n, m, q, a[N], b[N];

signed main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i <= m; ++i) std::cin >> b[i];
  for (int l1, r1, l2, r2; q; --q) {
    std::cin >> l1 >> r1 >> l2 >> r2;
    std::array<int, 4> x = {-INF, INF, -INF, INF}, y = {-INF, INF, -INF, INF};
    for (int i = l1; i <= r1; ++i) {
      if (a[i] >= 0) {
        x[0] = std::max(x[0], a[i]);
        x[1] = std::min(x[1], a[i]);
      } else {
        x[2] = std::max(x[2], a[i]);
        x[3] = std::min(x[3], a[i]);
      }
    }
    for (int i = l2; i <= r2; ++i) {
      if (b[i] >= 0) {
        y[0] = std::max(y[0], b[i]);
        y[1] = std::min(y[1], b[i]);
      } else {
        y[2] = std::max(y[2], b[i]);
        y[3] = std::min(y[3], b[i]);
      }
    }
    if (llabs(y[0]) != INF && llabs(y[2]) != INF) { // 后手有正有负
      std::cout << std::max(x[1] * y[3], x[2] * y[0]) << '\n';
    } else if (llabs(y[0]) != INF) { // 后手只有正数
      if (llabs(x[0]) != INF) { // 先手有正数
        std::cout << x[0] * y[1] << '\n';
      } else { // 先手只有负数
        std::cout << x[2] * y[0] << '\n';
      }
    } else { // 后手只有负数
      if (llabs(x[2]) != INF) { // 先手有负数
        std::cout << x[3] * y[2] << '\n';
      } else { // 先手只有正数
        std::cout << x[1] * y[3] << '\n';
      }
    }
  }
  return 0;
}
9

@陶荣杰1 发现是策略出了问题，线段树没挂掉

1 个赞
10

已解决。此贴结。

错误原因是在x没有正数的情况下会出现 x[1]*y[3] > x[2]*y[0] 或反之的情况，但是这种概率很小，因此95pts。

11