关于线段树喜提暴力分的那些事

线段树 40 pts 求调

#include <stdio.h>
#define int long long
#define max(a, b) (a > b ? a : b)
const int inf = 1e9 + 1;
struct Tag {
  int set;
  int add;
};
struct node {
  int l, r;
  int ans;
  Tag tag;
};
int n, q;
node tree[4004000];
int a[1001000];
void setTo(int k, int a) {
  tree[k].tag.set = a;
  tree[k].tag.add = 0;
  tree[k].ans = a;
}
void add(int k, int a) {
  if (tree[k].tag.set != inf) {
    setTo(k, a + tree[k].tag.set);
  } else {
    tree[k].tag.add += a;
    tree[k].ans += a;
  }
}
void pushUp(int k) { tree[k].ans = max(tree[k * 2].ans, tree[k * 2 + 1].ans); }
void pushDown(int k) {
  if (tree[k].tag.set != inf) {
    setTo(k * 2, tree[k].tag.set);
    setTo(k * 2 + 1, tree[k].tag.set);
  }
  add(k * 2, tree[k].tag.add);
  add(k * 2 + 1, tree[k].tag.add);
  tree[k].tag.add = 0;
}
void build(int i, int l, int r) {
  tree[i].l = l, tree[i].r = r;
  tree[i].tag.set = inf;
  if (l == r) {
    tree[i].ans = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(i * 2, l, mid);
  build(i * 2 + 1, mid + 1, r);
  pushUp(i);
}
void change(int i, int L, int R, int k, bool isAdd) {
  int l = tree[i].l, r = tree[i].r;
  if (r < L || R < l) {
    return;
  }
  if (L <= l && r <= R) {
    if (isAdd) {
      add(i, k);
    } else {
      setTo(i, k);
    }
    return;
  }
  pushDown(i);
  change(i * 2, L, R, k, isAdd);
  change(i * 2 + 1, L, R, k, isAdd);
  pushUp(i);
}
int query(int i, int L, int R) {
  int l = tree[i].l, r = tree[i].r;
  if (r < L || R < l) {
    return -inf;
  }
  if (L <= l && r <= R) {
    return tree[i].ans;
  }
  pushDown(i);
  return max(query(i * 2, L, R), query(i * 2 + 1, L, R));
}
signed main() {
  scanf("%lld%lld", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", a + i);
  }
  build(1, 1, n);
  while (q--) {
    int op, x, y;
    scanf("%lld%lld%lld", &op, &x, &y);
    if (op == 3) {
      printf("%lld\n", query(1, x, y));
    } else {
      int z;
      scanf("%lld", &z);
      change(1, x, y, z, op - 1);
    }
  }
  return 0;
}

提交记录