线段树3

区间历史最高

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

int re, zf; char c;
int read() {                       //读取键盘输入的内容
  re = 0; zf = 1;
  c = getchar(); while (c < '0' || c > '9') {if (c == '-') zf = -zf; c = getchar();}
  while (c >= '0' && c <= '9') {
    re = (re << 3) + (re << 1) + c - '0';
    c = getchar();
  }
  return zf * re;
}

void writee(ll x) {
  if (x > 9) writee(x / 10), x %= 10;
  putchar(x + '0');               //数字转化成字符输出
}

void write(ll x) {
  if (x < 0) putchar('-'), x = -x;
  writee(x);
  putchar('\n');
}

const int N = 500001;
int n, m, a[N], op, l, r, x;

struct XD_tree {
  ll sum[N << 2];
  int add_a[N << 2], add_b[N << 2], add_a1[N << 2], add_b1[N << 2];
  int ls[N << 2], rs[N << 2], maxa[N << 2], sec[N << 2], maxb[N << 2], cnt[N << 2];

  void up(int now) { //上传
    maxa[now] = max(maxa[now << 1], maxa[now << 1 | 1]);               //子节点最大值
    maxb[now] = max(maxb[now << 1], maxb[now << 1 | 1]);
    sum[now] = sum[now << 1] + sum[now << 1 | 1];                      //更新sum
    if (maxa[now << 1] == maxa[now << 1 | 1]) {                        //左右节点相同
      sec[now] = max(sec[now << 1], sec[now << 1 | 1]);                //更新第二最大值
      cnt[now] = cnt[now << 1] + cnt[now << 1 | 1];                    //左右节点的最大值的个数相加
    }
    else if (maxa[now << 1] > maxa[now << 1 | 1]) {                    //左节点比右节点权值大
      sec[now] = max(sec[now << 1], maxa[now << 1 | 1]);
      cnt[now] = cnt[now << 1];                                        //左儿子的cnt赋值给父节点
    }
    else {
      sec[now] = max(maxa[now << 1], sec[now << 1 | 1]);
      cnt[now] = cnt[now << 1 | 1];
    }
  }

  void update(int now, int k1, int k2, int k3, int k4) {               //k1:最大要加的 k2:历史最大要加的 k3:非最大要加的 k4:历史非最大要加的
    sum[now] += 1ll * k1 * cnt[now] + 1ll * k3 * (rs[now] - ls[now] + 1 - cnt[now]);               //更新sum
    maxb[now] = max(maxb[now], maxa[now] + k2);                        //历史最大值线段树
    add_b[now] = max(add_b[now], add_a[now] + k2);                     //历史最大值线段树的懒标记
    add_b1[now] = max(add_b1[now], add_a1[now] + k4);                  //非最大的懒标记
    maxa[now] += k1; add_a[now] += k1;                                 //区间最大数加上数值，区间最大值的加法的懒标记加上数值
    if (sec[now] != -1e9) {sec[now] += k3; add_a1[now] += k3;}         //叶节点的sec和add_a标记不做操作
  }

  void down(int now) {                                                 //下传
    int x = max(maxa[now << 1], maxa[now << 1 | 1]);                   //这里不能用 maxa[now]，因为你上面打标记的时候就加上了新加的值
    if (maxa[now << 1] == x) update(now << 1, add_a[now], add_b[now], add_a1[now], add_b1[now]);    //如果左节点大于等于右节点，k1使用区间最大值，k2使用历史区间最大值
    else update(now << 1, add_a1[now], add_b1[now], add_a1[now], add_b1[now]);                      //否则使用非最大值的懒标记
    if (maxa[now << 1 | 1] == x) update(now << 1 | 1, add_a[now], add_b[now], add_a1[now], add_b1[now]); 
    else update(now << 1 | 1, add_a1[now], add_b1[now], add_a1[now], add_b1[now]);
    add_a[now] = add_b[now] = add_a1[now] = add_b1[now] = 0;          //标记清空
}

  void build(int now, int l, int r) {                                 //建树
    ls[now] = l; rs[now] = r;
    if (l == r) {
      sum[now] = maxa[now] = maxb[now] = a[l];                        //叶节点：区间和=区间最大数=区间历史最大数
      sec[now] = -1e9; cnt[now] = 1;                                  //区间第二大数、区间最大数的个数
      return ;
    }
    int mid = (l + r) >> 1; build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
    up(now);
  }

  void update_add(int now) {
    if (ls[now] > r || rs[now] < l) return ;                          //剪枝：不在区间范围返回
    if (l <= ls[now] && rs[now] <= r) {                               //覆盖
      update(now, x, x, x, x); return ; //
    }
    down(now);
    update_add(now << 1); update_add(now << 1 | 1);
    up(now);
  }

  void update_min(int now) {
    if (ls[now] > r || rs[now] < l || x >= maxa[now]) return ;         //如果大于了最大，那一定不会更新
    if (l <= ls[now] && rs[now] <= r && x > sec[now]) {                //如果大于第二大，那肯定是只有最大值会改
      update(now, x - maxa[now], x - maxa[now], 0, 0); return ;        //相当于加负数补回去
    }
    down(now);                                                         //否则就继续递归下去
    update_min(now << 1); update_min(now << 1 | 1);
    up(now);
  }

  ll get_sum(int now) {                                                //递归拼凑出查询区间的元素总和
    if (ls[now] > r || rs[now] < l) return 0;
    if (l <= ls[now] && rs[now] <= r) return sum[now];
    down(now);
    return get_sum(now << 1) + get_sum(now << 1 | 1);
  }

  int get_maxa(int now) {                                              //最大值
    if (ls[now] > r || rs[now] < l) return -1e9;
    if (l <= ls[now] && rs[now] <= r) return maxa[now];
    down(now); return max(get_maxa(now << 1), get_maxa(now << 1 | 1));
  }

  int get_maxb(int now) {                                              //历史最大值
    if (ls[now] > r || rs[now] < l) return -1e9;
    if (l <= ls[now] && rs[now] <= r) return maxb[now];
    down(now); return max(get_maxb(now << 1), get_maxb(now << 1 | 1));
  }
}T;

int main() {
  n = read(); m = read();                                              //数组长度、操作次数
  for (int i = 1; i <= n; i++) a[i] = read();                          //读取数组
  T.build(1, 1, n);
  while (m--) {
    op = read(); l = read(); r = read();
    if (op == 1) x = read(), T.update_add(1);
    if (op == 2) x = read(), T.update_min(1);
    if (op == 3) write(T.get_sum(1));
    if (op == 4) write(T.get_maxa(1));
    if (op == 5) write(T.get_maxb(1));
  }
  return 0;
}

笔记：这个历史数值一般会输出三大类：①历史最大值②历史最小值③历史和。这个题目添加了一个历史最大值的输出，在维护上就多了一个储存历史纪录的线段树，和两个历史纪录的懒标记，下传函数update维护了四个赖标记，程序的核心思想使用的是吉老师线段树，下面的链接我放了他写的详解ppt

集训队论文