(N + Q) log N, TLE on 10 求助
查看原帖
(N + Q) log N, TLE on 10 求助
989792
lrx___楼主2025/6/20 20:25

record

#ifdef LOCAL_TEST
#include "D:/C++/include/all.h"
#else
#define debug(...)
#define cpp_version_ __cplusplus
#endif
#include <bits/stdc++.h>
#undef cpp_version_

using namespace std;
using bool_t = unsigned char;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

void fast_io() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
template <typename T> void ckmax(T &a, T b) {
  if (a < b) a = b;
}
template <typename T> void ckmin(T &a, T b) {
  if (b < a) a = b;
}

constexpr int MAXN = 5e5 + 5;
constexpr i64 INF = 1e18;
int N, Q;
i64 a[3][MAXN];
vector<pair<int, int>> itvs[MAXN];

i64 f[MAXN], ans = -INF;

struct segment_tree_1 {
  struct node {
    int l, r;
    i64 maxv;
  } t[MAXN << 2];
#define ls u << 1
#define rs u << 1 | 1
  void push_up(int u) {
    t[u].maxv = max(t[ls].maxv, t[rs].maxv);
  }
  void build(int u=1, int l=1, int r=N) {
    t[u].l = l;
    t[u].r = r;
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(u);
  }
  void update(int x, i64 k, int u=1) {
    if (t[u].l == t[u].r) {
      t[u].maxv = k;
      return;
    }
    x <= t[ls].r ? update(x, k, ls) : update(x, k, rs);
    push_up(u);
  }
  i64 query(int x, int y, int u=1) {
    if (t[u].r < x || y < t[u].l || x > y) return -INF;
    if (x <= t[u].l && t[u].r <= y) return t[u].maxv;
    return max(query(x, y, ls), query(x, y, rs));
  }
#undef ls
#undef rs
} s1, s2;
struct segment_tree_2 {
  struct node {
    int l, r;
    i64 maxf, maxg, ans;
    node operator+(const node& o) const {
      // debug("merge {} {}\n", maxf, o.maxg);
      return node{
        l,
        o.r,
        max(maxf, o.maxf),
        max(maxg, o.maxg),
        max({ans, o.ans, maxf + o.maxg})
      };
    }
  } t[MAXN << 2];
#define ls u << 1
#define rs u << 1 | 1
  void push_up(int u) {
    t[u] = t[ls] + t[rs];
  }
  void build(int u=1, int l=1, int r=N) {
    t[u].l = l;
    t[u].r = r;
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(u);
  }
  void update(int x, i64 f, i64 g, int u=1) {
    if (t[u].l == t[u].r) {
      t[u].maxf = f;
      t[u].maxg = g;
      t[u].ans = -INF;
      return;
    }
    x <= t[ls].r ? update(x, f, g, ls) : update(x, f, g, rs);
    push_up(u);
  }
  node query(int x, int y, int u=1) {
    if (x <= t[u].l && t[u].r <= y) return t[u];
    if (x <= t[ls].r && t[ls].r < y) return query(x, y, ls) + query(x, y, rs);
    if (x <= t[ls].r) return query(x, y, ls);
    return query(x, y, rs);
  }
#undef ls
#undef rs
} s3, s4;

template <int i>
i64 sum(int l, int r) {
  static_assert(0 <= i && i < 3);
  return a[i][r] - a[i][l - 1];
}
int main() {
  cin >> N >> Q;
  for (int i = 0; i < 3; ++i) {
    for (int j = 1; j <= N; ++j) {
      cin >> a[i][j];
      a[i][j] += a[i][j - 1];
    }
  }
  for (int i = 0, l, r, k; i < Q; ++i) {
    cin >> l >> r >> k;
    itvs[r].emplace_back(l, k);
  }

  s1.build();
  s2.build();
  s3.build();
  s4.build();
  for (int i = 1; i <= N; ++i) {
    f[i] = -INF;
    s2.update(i, sum<0>(1, i) - sum<1>(1, i - 1));
    for (const auto &[l, k] : itvs[i]) {
      ckmax(f[i], s1.query(max(l - 1, 1), i - 1) + sum<1>(1, i) - k);
      ckmax(f[i], s2.query(l, i) + sum<1>(1, i) - k);
    }
    // debug("f[{}] = {}\n", i, f[i]);
    s1.update(i, f[i] - sum<1>(1, i));
    // debug("! {} + {}\n", f[i], sum<2>(i, N));
    ckmax(ans, f[i] + sum<2>(i, N));
    s3.update(i, f[i] - sum<1>(1, i), sum<1>(1, i) - sum<2>(1, i - 1));
    s4.update(i, sum<0>(1, i) - sum<1>(1, i - 1), sum<1>(1, i) - sum<2>(1, i - 1));
    if (i > 1) {
      for (const auto &[l, k] : itvs[i]) {
        // debug("@ {} + {} - {}\n", s3.query(max(l - 1, 1), i - 1).ans, sum<2>(1, N), k);
        if (max(l - 1, 1) <= i - 1) {
          ckmax(ans, s3.query(max(l - 1, 1), i - 1).ans + sum<2>(1, N) - k);
        }
        // debug("# {} + {} - {}\n", s4.query(l, i - 1).ans, sum<2>(1, N), k);
        if (l <= i - 1) {
          ckmax(ans, s4.query(l, i - 1).ans + sum<2>(1, N) - k);
        }
      }
    }                                
  }
  cout << ans << '\n';
  return 0;
}

2025/6/20 20:25
加载中...